Commit | Line | Data |
---|---|---|
2ba45a60 DM |
1 | /* |
2 | * seek utility functions for use within format handlers | |
3 | * | |
4 | * Copyright (c) 2009 Ivan Schreter | |
5 | * | |
6 | * This file is part of FFmpeg. | |
7 | * | |
8 | * FFmpeg is free software; you can redistribute it and/or | |
9 | * modify it under the terms of the GNU Lesser General Public | |
10 | * License as published by the Free Software Foundation; either | |
11 | * version 2.1 of the License, or (at your option) any later version. | |
12 | * | |
13 | * FFmpeg is distributed in the hope that it will be useful, | |
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
16 | * Lesser General Public License for more details. | |
17 | * | |
18 | * You should have received a copy of the GNU Lesser General Public | |
19 | * License along with FFmpeg; if not, write to the Free Software | |
20 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
21 | */ | |
22 | ||
23 | #include <stdint.h> | |
24 | ||
25 | #include "seek.h" | |
26 | #include "libavutil/mathematics.h" | |
27 | #include "libavutil/mem.h" | |
28 | #include "internal.h" | |
29 | ||
30 | // NOTE: implementation should be moved here in another patch, to keep patches | |
31 | // separated. | |
32 | ||
33 | /** | |
34 | * helper structure describing keyframe search state of one stream | |
35 | */ | |
36 | typedef struct { | |
37 | int64_t pos_lo; ///< position of the frame with low timestamp in file or INT64_MAX if not found (yet) | |
38 | int64_t ts_lo; ///< frame presentation timestamp or same as pos_lo for byte seeking | |
39 | ||
40 | int64_t pos_hi; ///< position of the frame with high timestamp in file or INT64_MAX if not found (yet) | |
41 | int64_t ts_hi; ///< frame presentation timestamp or same as pos_hi for byte seeking | |
42 | ||
43 | int64_t last_pos; ///< last known position of a frame, for multi-frame packets | |
44 | ||
45 | int64_t term_ts; ///< termination timestamp (which TS we already read) | |
46 | AVRational term_ts_tb; ///< timebase for term_ts | |
47 | int64_t first_ts; ///< first packet timestamp in this iteration (to fill term_ts later) | |
48 | AVRational first_ts_tb; ///< timebase for first_ts | |
49 | ||
50 | int terminated; ///< termination flag for the current iteration | |
51 | } AVSyncPoint; | |
52 | ||
53 | /** | |
54 | * Compute a distance between timestamps. | |
55 | * | |
56 | * Distances are only comparable, if same time bases are used for computing | |
57 | * distances. | |
58 | * | |
59 | * @param ts_hi high timestamp | |
60 | * @param tb_hi high timestamp time base | |
61 | * @param ts_lo low timestamp | |
62 | * @param tb_lo low timestamp time base | |
63 | * @return representation of distance between high and low timestamps | |
64 | */ | |
65 | static int64_t ts_distance(int64_t ts_hi, | |
66 | AVRational tb_hi, | |
67 | int64_t ts_lo, | |
68 | AVRational tb_lo) | |
69 | { | |
70 | int64_t hi, lo; | |
71 | ||
72 | hi = ts_hi * tb_hi.num * tb_lo.den; | |
73 | lo = ts_lo * tb_lo.num * tb_hi.den; | |
74 | ||
75 | return hi - lo; | |
76 | } | |
77 | ||
78 | /** | |
79 | * Partial search for keyframes in multiple streams. | |
80 | * | |
81 | * This routine searches in each stream for the next lower and the next higher | |
82 | * timestamp compared to the given target timestamp. The search starts at the current | |
83 | * file position and ends at the file position, where all streams have already been | |
84 | * examined (or when all higher key frames are found in the first iteration). | |
85 | * | |
86 | * This routine is called iteratively with an exponential backoff to find the lower | |
87 | * timestamp. | |
88 | * | |
89 | * @param s format context | |
90 | * @param timestamp target timestamp (or position, if AVSEEK_FLAG_BYTE) | |
91 | * @param timebase time base for timestamps | |
92 | * @param flags seeking flags | |
93 | * @param sync array with information per stream | |
94 | * @param keyframes_to_find count of keyframes to find in total | |
95 | * @param found_lo ptr to the count of already found low timestamp keyframes | |
96 | * @param found_hi ptr to the count of already found high timestamp keyframes | |
97 | * @param first_iter flag for first iteration | |
98 | */ | |
99 | static void search_hi_lo_keyframes(AVFormatContext *s, | |
100 | int64_t timestamp, | |
101 | AVRational timebase, | |
102 | int flags, | |
103 | AVSyncPoint *sync, | |
104 | int keyframes_to_find, | |
105 | int *found_lo, | |
106 | int *found_hi, | |
107 | int first_iter) | |
108 | { | |
109 | AVPacket pkt; | |
110 | AVSyncPoint *sp; | |
111 | AVStream *st; | |
112 | int idx; | |
113 | int flg; | |
114 | int terminated_count = 0; | |
115 | int64_t pos; | |
116 | int64_t pts, dts; // PTS/DTS from stream | |
117 | int64_t ts; // PTS in stream-local time base or position for byte seeking | |
118 | AVRational ts_tb; // Time base of the stream or 1:1 for byte seeking | |
119 | ||
120 | for (;;) { | |
121 | if (av_read_frame(s, &pkt) < 0) { | |
122 | // EOF or error, make sure high flags are set | |
123 | for (idx = 0; idx < s->nb_streams; ++idx) { | |
124 | if (s->streams[idx]->discard < AVDISCARD_ALL) { | |
125 | sp = &sync[idx]; | |
126 | if (sp->pos_hi == INT64_MAX) { | |
127 | // no high frame exists for this stream | |
128 | (*found_hi)++; | |
129 | sp->ts_hi = INT64_MAX; | |
130 | sp->pos_hi = INT64_MAX - 1; | |
131 | } | |
132 | } | |
133 | } | |
134 | break; | |
135 | } | |
136 | ||
137 | idx = pkt.stream_index; | |
138 | st = s->streams[idx]; | |
139 | if (st->discard >= AVDISCARD_ALL) | |
140 | // this stream is not active, skip packet | |
141 | continue; | |
142 | ||
143 | sp = &sync[idx]; | |
144 | ||
145 | flg = pkt.flags; | |
146 | pos = pkt.pos; | |
147 | pts = pkt.pts; | |
148 | dts = pkt.dts; | |
149 | if (pts == AV_NOPTS_VALUE) | |
150 | // some formats don't provide PTS, only DTS | |
151 | pts = dts; | |
152 | ||
153 | av_free_packet(&pkt); | |
154 | ||
155 | // Multi-frame packets only return position for the very first frame. | |
156 | // Other frames are read with position == -1. Therefore, we note down | |
157 | // last known position of a frame and use it if a frame without | |
158 | // position arrives. In this way, it's possible to seek to proper | |
159 | // position. Additionally, for parsers not providing position at all, | |
160 | // an approximation will be used (starting position of this iteration). | |
161 | if (pos < 0) | |
162 | pos = sp->last_pos; | |
163 | else | |
164 | sp->last_pos = pos; | |
165 | ||
166 | // Evaluate key frames with known TS (or any frames, if AVSEEK_FLAG_ANY set). | |
167 | if (pts != AV_NOPTS_VALUE && | |
168 | ((flg & AV_PKT_FLAG_KEY) || (flags & AVSEEK_FLAG_ANY))) { | |
169 | if (flags & AVSEEK_FLAG_BYTE) { | |
170 | // for byte seeking, use position as timestamp | |
171 | ts = pos; | |
172 | ts_tb.num = 1; | |
173 | ts_tb.den = 1; | |
174 | } else { | |
175 | // otherwise, get stream time_base | |
176 | ts = pts; | |
177 | ts_tb = st->time_base; | |
178 | } | |
179 | ||
180 | if (sp->first_ts == AV_NOPTS_VALUE) { | |
181 | // Note down termination timestamp for the next iteration - when | |
182 | // we encounter a packet with the same timestamp, we will ignore | |
183 | // any further packets for this stream in next iteration (as they | |
184 | // are already evaluated). | |
185 | sp->first_ts = ts; | |
186 | sp->first_ts_tb = ts_tb; | |
187 | } | |
188 | ||
189 | if (sp->term_ts != AV_NOPTS_VALUE && | |
190 | av_compare_ts(ts, ts_tb, sp->term_ts, sp->term_ts_tb) > 0) { | |
191 | // past the end position from last iteration, ignore packet | |
192 | if (!sp->terminated) { | |
193 | sp->terminated = 1; | |
194 | ++terminated_count; | |
195 | if (sp->pos_hi == INT64_MAX) { | |
196 | // no high frame exists for this stream | |
197 | (*found_hi)++; | |
198 | sp->ts_hi = INT64_MAX; | |
199 | sp->pos_hi = INT64_MAX - 1; | |
200 | } | |
201 | if (terminated_count == keyframes_to_find) | |
202 | break; // all terminated, iteration done | |
203 | } | |
204 | continue; | |
205 | } | |
206 | ||
207 | if (av_compare_ts(ts, ts_tb, timestamp, timebase) <= 0) { | |
208 | // keyframe found before target timestamp | |
209 | if (sp->pos_lo == INT64_MAX) { | |
210 | // found first keyframe lower than target timestamp | |
211 | (*found_lo)++; | |
212 | sp->ts_lo = ts; | |
213 | sp->pos_lo = pos; | |
214 | } else if (sp->ts_lo < ts) { | |
215 | // found a better match (closer to target timestamp) | |
216 | sp->ts_lo = ts; | |
217 | sp->pos_lo = pos; | |
218 | } | |
219 | } | |
220 | if (av_compare_ts(ts, ts_tb, timestamp, timebase) >= 0) { | |
221 | // keyframe found after target timestamp | |
222 | if (sp->pos_hi == INT64_MAX) { | |
223 | // found first keyframe higher than target timestamp | |
224 | (*found_hi)++; | |
225 | sp->ts_hi = ts; | |
226 | sp->pos_hi = pos; | |
227 | if (*found_hi >= keyframes_to_find && first_iter) { | |
228 | // We found high frame for all. They may get updated | |
229 | // to TS closer to target TS in later iterations (which | |
230 | // will stop at start position of previous iteration). | |
231 | break; | |
232 | } | |
233 | } else if (sp->ts_hi > ts) { | |
234 | // found a better match (actually, shouldn't happen) | |
235 | sp->ts_hi = ts; | |
236 | sp->pos_hi = pos; | |
237 | } | |
238 | } | |
239 | } | |
240 | } | |
241 | ||
242 | // Clean up the parser. | |
243 | ff_read_frame_flush(s); | |
244 | } | |
245 | ||
246 | int64_t ff_gen_syncpoint_search(AVFormatContext *s, | |
247 | int stream_index, | |
248 | int64_t pos, | |
249 | int64_t ts_min, | |
250 | int64_t ts, | |
251 | int64_t ts_max, | |
252 | int flags) | |
253 | { | |
254 | AVSyncPoint *sync, *sp; | |
255 | AVStream *st; | |
256 | int i; | |
257 | int keyframes_to_find = 0; | |
258 | int64_t curpos; | |
259 | int64_t step; | |
260 | int found_lo = 0, found_hi = 0; | |
261 | int64_t min_distance, distance; | |
262 | int64_t min_pos = 0; | |
263 | int first_iter = 1; | |
264 | AVRational time_base; | |
265 | ||
266 | if (flags & AVSEEK_FLAG_BYTE) { | |
267 | // for byte seeking, we have exact 1:1 "timestamps" - positions | |
268 | time_base.num = 1; | |
269 | time_base.den = 1; | |
270 | } else { | |
271 | if (stream_index >= 0) { | |
272 | // we have a reference stream, which time base we use | |
273 | st = s->streams[stream_index]; | |
274 | time_base = st->time_base; | |
275 | } else { | |
276 | // no reference stream, use AV_TIME_BASE as reference time base | |
277 | time_base.num = 1; | |
278 | time_base.den = AV_TIME_BASE; | |
279 | } | |
280 | } | |
281 | ||
282 | // Initialize syncpoint structures for each stream. | |
283 | sync = av_malloc_array(s->nb_streams, sizeof(AVSyncPoint)); | |
284 | if (!sync) | |
285 | // cannot allocate helper structure | |
286 | return -1; | |
287 | ||
288 | for (i = 0; i < s->nb_streams; ++i) { | |
289 | st = s->streams[i]; | |
290 | sp = &sync[i]; | |
291 | ||
292 | sp->pos_lo = INT64_MAX; | |
293 | sp->ts_lo = INT64_MAX; | |
294 | sp->pos_hi = INT64_MAX; | |
295 | sp->ts_hi = INT64_MAX; | |
296 | sp->terminated = 0; | |
297 | sp->first_ts = AV_NOPTS_VALUE; | |
298 | sp->term_ts = ts_max; | |
299 | sp->term_ts_tb = time_base; | |
300 | sp->last_pos = pos; | |
301 | ||
302 | st->cur_dts = AV_NOPTS_VALUE; | |
303 | ||
304 | if (st->discard < AVDISCARD_ALL) | |
305 | ++keyframes_to_find; | |
306 | } | |
307 | ||
308 | if (!keyframes_to_find) { | |
309 | // no stream active, error | |
310 | av_free(sync); | |
311 | return -1; | |
312 | } | |
313 | ||
314 | // Find keyframes in all active streams with timestamp/position just before | |
315 | // and just after requested timestamp/position. | |
316 | step = s->pb->buffer_size; | |
317 | curpos = FFMAX(pos - step / 2, 0); | |
318 | for (;;) { | |
319 | avio_seek(s->pb, curpos, SEEK_SET); | |
320 | search_hi_lo_keyframes(s, | |
321 | ts, time_base, | |
322 | flags, | |
323 | sync, | |
324 | keyframes_to_find, | |
325 | &found_lo, &found_hi, | |
326 | first_iter); | |
327 | if (found_lo == keyframes_to_find && found_hi == keyframes_to_find) | |
328 | break; // have all keyframes we wanted | |
329 | if (!curpos) | |
330 | break; // cannot go back anymore | |
331 | ||
332 | curpos = pos - step; | |
333 | if (curpos < 0) | |
334 | curpos = 0; | |
335 | step *= 2; | |
336 | ||
337 | // switch termination positions | |
338 | for (i = 0; i < s->nb_streams; ++i) { | |
339 | st = s->streams[i]; | |
340 | st->cur_dts = AV_NOPTS_VALUE; | |
341 | ||
342 | sp = &sync[i]; | |
343 | if (sp->first_ts != AV_NOPTS_VALUE) { | |
344 | sp->term_ts = sp->first_ts; | |
345 | sp->term_ts_tb = sp->first_ts_tb; | |
346 | sp->first_ts = AV_NOPTS_VALUE; | |
347 | } | |
348 | sp->terminated = 0; | |
349 | sp->last_pos = curpos; | |
350 | } | |
351 | first_iter = 0; | |
352 | } | |
353 | ||
354 | // Find actual position to start decoding so that decoder synchronizes | |
355 | // closest to ts and between ts_min and ts_max. | |
356 | pos = INT64_MAX; | |
357 | ||
358 | for (i = 0; i < s->nb_streams; ++i) { | |
359 | st = s->streams[i]; | |
360 | if (st->discard < AVDISCARD_ALL) { | |
361 | sp = &sync[i]; | |
362 | min_distance = INT64_MAX; | |
363 | // Find timestamp closest to requested timestamp within min/max limits. | |
364 | if (sp->pos_lo != INT64_MAX | |
365 | && av_compare_ts(ts_min, time_base, sp->ts_lo, st->time_base) <= 0 | |
366 | && av_compare_ts(sp->ts_lo, st->time_base, ts_max, time_base) <= 0) { | |
367 | // low timestamp is in range | |
368 | min_distance = ts_distance(ts, time_base, sp->ts_lo, st->time_base); | |
369 | min_pos = sp->pos_lo; | |
370 | } | |
371 | if (sp->pos_hi != INT64_MAX | |
372 | && av_compare_ts(ts_min, time_base, sp->ts_hi, st->time_base) <= 0 | |
373 | && av_compare_ts(sp->ts_hi, st->time_base, ts_max, time_base) <= 0) { | |
374 | // high timestamp is in range, check distance | |
375 | distance = ts_distance(sp->ts_hi, st->time_base, ts, time_base); | |
376 | if (distance < min_distance) { | |
377 | min_distance = distance; | |
378 | min_pos = sp->pos_hi; | |
379 | } | |
380 | } | |
381 | if (min_distance == INT64_MAX) { | |
382 | // no timestamp is in range, cannot seek | |
383 | av_free(sync); | |
384 | return -1; | |
385 | } | |
386 | if (min_pos < pos) | |
387 | pos = min_pos; | |
388 | } | |
389 | } | |
390 | ||
391 | avio_seek(s->pb, pos, SEEK_SET); | |
392 | av_free(sync); | |
393 | return pos; | |
394 | } | |
395 | ||
396 | AVParserState *ff_store_parser_state(AVFormatContext *s) | |
397 | { | |
398 | int i; | |
399 | AVStream *st; | |
400 | AVParserStreamState *ss; | |
401 | AVParserState *state = av_malloc(sizeof(AVParserState)); | |
402 | if (!state) | |
403 | return NULL; | |
404 | ||
405 | state->stream_states = av_malloc_array(s->nb_streams, sizeof(AVParserStreamState)); | |
406 | if (!state->stream_states) { | |
407 | av_free(state); | |
408 | return NULL; | |
409 | } | |
410 | ||
411 | state->fpos = avio_tell(s->pb); | |
412 | ||
413 | // copy context structures | |
414 | state->packet_buffer = s->packet_buffer; | |
415 | state->parse_queue = s->parse_queue; | |
416 | state->raw_packet_buffer = s->raw_packet_buffer; | |
417 | state->raw_packet_buffer_remaining_size = s->raw_packet_buffer_remaining_size; | |
418 | ||
419 | s->packet_buffer = NULL; | |
420 | s->parse_queue = NULL; | |
421 | s->raw_packet_buffer = NULL; | |
422 | s->raw_packet_buffer_remaining_size = RAW_PACKET_BUFFER_SIZE; | |
423 | ||
424 | // copy stream structures | |
425 | state->nb_streams = s->nb_streams; | |
426 | for (i = 0; i < s->nb_streams; i++) { | |
427 | st = s->streams[i]; | |
428 | ss = &state->stream_states[i]; | |
429 | ||
430 | ss->parser = st->parser; | |
431 | ss->last_IP_pts = st->last_IP_pts; | |
432 | ss->cur_dts = st->cur_dts; | |
433 | ss->probe_packets = st->probe_packets; | |
434 | ||
435 | st->parser = NULL; | |
436 | st->last_IP_pts = AV_NOPTS_VALUE; | |
437 | st->cur_dts = AV_NOPTS_VALUE; | |
438 | st->probe_packets = MAX_PROBE_PACKETS; | |
439 | } | |
440 | ||
441 | return state; | |
442 | } | |
443 | ||
444 | void ff_restore_parser_state(AVFormatContext *s, AVParserState *state) | |
445 | { | |
446 | int i; | |
447 | AVStream *st; | |
448 | AVParserStreamState *ss; | |
449 | ff_read_frame_flush(s); | |
450 | ||
451 | if (!state) | |
452 | return; | |
453 | ||
454 | avio_seek(s->pb, state->fpos, SEEK_SET); | |
455 | ||
456 | // copy context structures | |
457 | s->packet_buffer = state->packet_buffer; | |
458 | s->parse_queue = state->parse_queue; | |
459 | s->raw_packet_buffer = state->raw_packet_buffer; | |
460 | s->raw_packet_buffer_remaining_size = state->raw_packet_buffer_remaining_size; | |
461 | ||
462 | // copy stream structures | |
463 | for (i = 0; i < state->nb_streams; i++) { | |
464 | st = s->streams[i]; | |
465 | ss = &state->stream_states[i]; | |
466 | ||
467 | st->parser = ss->parser; | |
468 | st->last_IP_pts = ss->last_IP_pts; | |
469 | st->cur_dts = ss->cur_dts; | |
470 | st->probe_packets = ss->probe_packets; | |
471 | } | |
472 | ||
473 | av_free(state->stream_states); | |
474 | av_free(state); | |
475 | } | |
476 | ||
477 | static void free_packet_list(AVPacketList *pktl) | |
478 | { | |
479 | AVPacketList *cur; | |
480 | while (pktl) { | |
481 | cur = pktl; | |
482 | pktl = cur->next; | |
483 | av_free_packet(&cur->pkt); | |
484 | av_free(cur); | |
485 | } | |
486 | } | |
487 | ||
488 | void ff_free_parser_state(AVFormatContext *s, AVParserState *state) | |
489 | { | |
490 | int i; | |
491 | AVParserStreamState *ss; | |
492 | ||
493 | if (!state) | |
494 | return; | |
495 | ||
496 | for (i = 0; i < state->nb_streams; i++) { | |
497 | ss = &state->stream_states[i]; | |
498 | if (ss->parser) | |
499 | av_parser_close(ss->parser); | |
500 | } | |
501 | ||
502 | free_packet_list(state->packet_buffer); | |
503 | free_packet_list(state->parse_queue); | |
504 | free_packet_list(state->raw_packet_buffer); | |
505 | ||
506 | av_free(state->stream_states); | |
507 | av_free(state); | |
508 | } |