Mercurial > libavformat.hg
comparison seek.c @ 5139:9b2d2f4aa042 libavformat
Support for generic multi-stream key frame finding for new seek API.
author | schreter |
---|---|
date | Sat, 22 Aug 2009 16:05:43 +0000 |
parents | |
children | 26ba0ebacbb2 |
comparison
equal
deleted
inserted
replaced
5138:ad4e3a0bd4bd | 5139:9b2d2f4aa042 |
---|---|
1 /* | |
2 * Utility functions for seeking for use within FFmpeg 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 "seek.h" | |
24 #include "libavutil/mem.h" | |
25 | |
26 // NOTE: implementation should be moved here in another patch, to keep patches | |
27 // separated. | |
28 extern void av_read_frame_flush(AVFormatContext *s); | |
29 | |
30 /** | |
31 * Helper structure to store parser state of AVStream. | |
32 */ | |
33 typedef struct AVStreamState { | |
34 // Saved members of AVStream | |
35 AVCodecParserContext *parser; | |
36 AVPacket cur_pkt; | |
37 int64_t last_IP_pts; | |
38 int64_t cur_dts; | |
39 int64_t reference_dts; | |
40 const uint8_t *cur_ptr; | |
41 int cur_len; | |
42 int probe_packets; | |
43 } AVStreamState; | |
44 | |
45 /** | |
46 * Helper structure to store parser state of AVFormat. | |
47 */ | |
48 struct AVParserState { | |
49 int64_t fpos; ///< File position at the time of call. | |
50 | |
51 // Saved members of AVFormatContext | |
52 AVStream *cur_st; ///< Current stream. | |
53 AVPacketList *packet_buffer; ///< Packet buffer of original state. | |
54 AVPacketList *raw_packet_buffer; ///< Raw packet buffer of original state. | |
55 int raw_packet_buffer_remaining_size; ///< Remaining size available for raw_packet_buffer. | |
56 | |
57 // Saved info for streams. | |
58 int nb_streams; ///< Number of streams with stored state. | |
59 AVStreamState *stream_states; ///< States of individual streams (array). | |
60 }; | |
61 | |
62 /** | |
63 * Helper structure describing keyframe search state of one stream. | |
64 */ | |
65 typedef struct { | |
66 int64_t pos_lo; ///< Position of the frame with low timestamp in file or INT64_MAX if not found (yet). | |
67 int64_t ts_lo; ///< Frame presentation timestamp or same as pos_lo for byte seeking. | |
68 | |
69 int64_t pos_hi; ///< Position of the frame with high timestamp in file or INT64_MAX if not found (yet). | |
70 int64_t ts_hi; ///< Frame presentation timestamp or same as pos_hi for byte seeking. | |
71 | |
72 int64_t last_pos; ///< Last known position of a frame, for multi-frame packets. | |
73 | |
74 int64_t term_ts; ///< Termination timestamp (which TS we already read). | |
75 AVRational term_ts_tb; ///< Timebase for term_ts. | |
76 int64_t first_ts; ///< First packet timestamp in this iteration (to fill term_ts later). | |
77 AVRational first_ts_tb;///< Timebase for first_ts. | |
78 | |
79 int terminated; ///< Termination flag for current iteration. | |
80 } AVSyncPoint; | |
81 | |
82 /** | |
83 * Compare two timestamps exactly, taking into account their respective time bases. | |
84 * | |
85 * @param ts_a timestamp A. | |
86 * @param tb_a time base for timestamp A. | |
87 * @param ts_b timestamp B. | |
88 * @param tb_b time base for timestamp A. | |
89 * @return -1. 0 or 1 if timestamp A is less than, equal or greater than timestamp B. | |
90 */ | |
91 static int compare_ts(int64_t ts_a, AVRational tb_a, int64_t ts_b, AVRational tb_b) | |
92 { | |
93 int64_t a, b, res; | |
94 | |
95 if (ts_a == INT64_MIN) | |
96 return ts_a < ts_b ? -1 : 0; | |
97 if (ts_a == INT64_MAX) | |
98 return ts_a > ts_b ? 1 : 0; | |
99 if (ts_b == INT64_MIN) | |
100 return ts_a > ts_b ? 1 : 0; | |
101 if (ts_b == INT64_MAX) | |
102 return ts_a < ts_b ? -1 : 0; | |
103 | |
104 a = ts_a * tb_a.num * tb_b.den; | |
105 b = ts_b * tb_b.num * tb_a.den; | |
106 | |
107 res = a - b; | |
108 if (res == 0) | |
109 return 0; | |
110 else | |
111 return (res >> 63) | 1; | |
112 } | |
113 | |
114 /** | |
115 * Compute a distance between timestamps. | |
116 * | |
117 * Distances are only comparable, if same time bases are used for computing | |
118 * distances. | |
119 * | |
120 * @param ts_hi high timestamp. | |
121 * @param tb_hi high timestamp time base. | |
122 * @param ts_lo low timestamp. | |
123 * @param tb_lo low timestamp time base. | |
124 * @return representation of distance between high and low timestamps. | |
125 */ | |
126 static int64_t ts_distance(int64_t ts_hi, AVRational tb_hi, int64_t ts_lo, AVRational tb_lo) | |
127 { | |
128 int64_t hi, lo; | |
129 | |
130 hi = ts_hi * tb_hi.num * tb_lo.den; | |
131 lo = ts_lo * tb_lo.num * tb_hi.den; | |
132 | |
133 return hi - lo; | |
134 } | |
135 | |
136 /** | |
137 * Partial search for keyframes in multiple streams. | |
138 * | |
139 * This routine searches for the next lower and next higher timestamp to | |
140 * given target timestamp in each stream, starting at current file position | |
141 * and ending at position, where all streams have already been examined | |
142 * (or when all higher key frames found in first iteration). | |
143 * | |
144 * This routine is called iteratively with exponential backoff to find lower | |
145 * timestamp. | |
146 * | |
147 * @param s format context. | |
148 * @param timestamp target timestamp (or position, if AVSEEK_FLAG_BYTE). | |
149 * @param timebase time base for timestamps. | |
150 * @param flags seeking flags. | |
151 * @param sync array with information per stream. | |
152 * @param keyframes_to_find count of keyframes to find in total. | |
153 * @param found_lo pointer to count of already found low timestamp keyframes. | |
154 * @param found_hi pointer to count of already found high timestamp keyframes. | |
155 * @param first_iter flag for first iteration. | |
156 */ | |
157 static void search_hi_lo_keyframes(AVFormatContext *s, | |
158 int64_t timestamp, | |
159 AVRational timebase, | |
160 int flags, | |
161 AVSyncPoint *sync, | |
162 int keyframes_to_find, | |
163 int *found_lo, | |
164 int *found_hi, | |
165 int first_iter) | |
166 { | |
167 AVPacket pkt; | |
168 AVSyncPoint *sp; | |
169 AVStream *st; | |
170 int idx; | |
171 int flg; | |
172 int terminated_count = 0; | |
173 int64_t pos; | |
174 int64_t pts, dts; // PTS/DTS from stream | |
175 int64_t ts; // PTS in stream-local time base or position for byte seeking | |
176 AVRational ts_tb; // Time base of the stream or 1:1 for byte seeking | |
177 | |
178 for (;;) { | |
179 if (av_read_frame(s, &pkt) < 0) { | |
180 // EOF or error, make sure high flags are set | |
181 for (idx = 0; idx < s->nb_streams; ++idx) { | |
182 if (s->streams[idx]->discard < AVDISCARD_ALL) { | |
183 sp = &sync[idx]; | |
184 if (sp->pos_hi == INT64_MAX) { | |
185 // No high frame exists for this stream | |
186 (*found_hi)++; | |
187 sp->ts_hi = INT64_MAX; | |
188 sp->pos_hi = INT64_MAX - 1; | |
189 } | |
190 } | |
191 } | |
192 break; | |
193 } | |
194 | |
195 idx = pkt.stream_index; | |
196 st = s->streams[idx]; | |
197 if (st->discard >= AVDISCARD_ALL) { | |
198 // This stream is not active, skip packet. | |
199 continue; | |
200 } | |
201 sp = &sync[idx]; | |
202 | |
203 flg = pkt.flags; | |
204 pos = pkt.pos; | |
205 pts = pkt.pts; | |
206 dts = pkt.dts; | |
207 if (pts == AV_NOPTS_VALUE) { | |
208 // Some formats don't provide PTS, only DTS. | |
209 pts = dts; | |
210 } | |
211 av_free_packet(&pkt); | |
212 | |
213 // Multi-frame packets only return position for the very first frame. | |
214 // Other frames are read with position == -1. Therefore, we note down | |
215 // last known position of a frame and use it if a frame without | |
216 // position arrives. In this way, it's possible to seek to proper | |
217 // position. Additionally, for parsers not providing position at all, | |
218 // an approximation will be used (starting position of this iteration). | |
219 if (pos < 0) { | |
220 pos = sp->last_pos; | |
221 } else { | |
222 sp->last_pos = pos; | |
223 } | |
224 | |
225 // Evaluate key frames with known TS (or any frames, if AVSEEK_FLAG_ANY set). | |
226 if (pts != AV_NOPTS_VALUE && ((flg & PKT_FLAG_KEY) || (flags & AVSEEK_FLAG_ANY))) { | |
227 if (flags & AVSEEK_FLAG_BYTE) { | |
228 // For byte seeking, use position as timestamp. | |
229 ts = pos; | |
230 ts_tb.num = 1; | |
231 ts_tb.den = 1; | |
232 } else { | |
233 // Get stream time_base. | |
234 ts = pts; | |
235 ts_tb = st->time_base; | |
236 } | |
237 | |
238 if (sp->first_ts == AV_NOPTS_VALUE) { | |
239 // Note down termination timestamp for the next iteration - when | |
240 // we encounter a packet with the same timestamp, we will ignore | |
241 // any further packets for this stream in next iteration (as they | |
242 // are already evaluated). | |
243 sp->first_ts = ts; | |
244 sp->first_ts_tb = ts_tb; | |
245 } | |
246 | |
247 if (sp->term_ts != AV_NOPTS_VALUE && compare_ts(ts, ts_tb, sp->term_ts, sp->term_ts_tb) > 0) { | |
248 // We are past the end position from last iteration, ignore packet. | |
249 if (!sp->terminated) { | |
250 sp->terminated = 1; | |
251 ++terminated_count; | |
252 if (sp->pos_hi == INT64_MAX) { | |
253 // No high frame exists for this stream | |
254 (*found_hi)++; | |
255 sp->ts_hi = INT64_MAX; | |
256 sp->pos_hi = INT64_MAX - 1; | |
257 } | |
258 if (terminated_count == keyframes_to_find) | |
259 break; // all terminated, iteration done | |
260 } | |
261 continue; | |
262 } | |
263 | |
264 if (compare_ts(ts, ts_tb, timestamp, timebase) <= 0) { | |
265 // Keyframe found before target timestamp. | |
266 if (sp->pos_lo == INT64_MAX) { | |
267 // Found first keyframe lower than target timestamp. | |
268 (*found_lo)++; | |
269 sp->ts_lo = ts; | |
270 sp->pos_lo = pos; | |
271 } else if (sp->ts_lo < ts) { | |
272 // Found a better match (closer to target timestamp). | |
273 sp->ts_lo = ts; | |
274 sp->pos_lo = pos; | |
275 } | |
276 } | |
277 if (compare_ts(ts, ts_tb, timestamp, timebase) >= 0) { | |
278 // Keyframe found after target timestamp. | |
279 if (sp->pos_hi == INT64_MAX) { | |
280 // Found first keyframe higher than target timestamp. | |
281 (*found_hi)++; | |
282 sp->ts_hi = ts; | |
283 sp->pos_hi = pos; | |
284 if (*found_hi >= keyframes_to_find && first_iter) { | |
285 // We found high frame for all. They may get updated | |
286 // to TS closer to target TS in later iterations (which | |
287 // will stop at start position of previous iteration). | |
288 break; | |
289 } | |
290 } else if (sp->ts_hi > ts) { | |
291 // Found a better match (actually, shouldn't happen). | |
292 sp->ts_hi = ts; | |
293 sp->pos_hi = pos; | |
294 } | |
295 } | |
296 } | |
297 } | |
298 | |
299 // Clean up the parser. | |
300 av_read_frame_flush(s); | |
301 } | |
302 | |
303 int64_t ff_gen_syncpoint_search(AVFormatContext *s, | |
304 int stream_index, | |
305 int64_t pos, | |
306 int64_t ts_min, | |
307 int64_t ts, | |
308 int64_t ts_max, | |
309 int flags) | |
310 { | |
311 AVSyncPoint *sync, *sp; | |
312 AVStream *st; | |
313 int i; | |
314 int keyframes_to_find = 0; | |
315 int64_t curpos; | |
316 int64_t step; | |
317 int found_lo = 0, found_hi = 0; | |
318 int64_t min_distance, distance; | |
319 int64_t min_pos = 0; | |
320 int first_iter = 1; | |
321 AVRational time_base; | |
322 | |
323 if (flags & AVSEEK_FLAG_BYTE) { | |
324 /* For byte seeking, we have exact 1:1 "timestamps" - positions */ | |
325 time_base.num = 1; | |
326 time_base.den = 1; | |
327 } else { | |
328 if (stream_index >= 0) { | |
329 /* We have a reference stream, which time base we use */ | |
330 st = s->streams[stream_index]; | |
331 time_base = st->time_base; | |
332 } else { | |
333 /* No reference stream, use AV_TIME_BASE as reference time base */ | |
334 time_base.num = 1; | |
335 time_base.den = AV_TIME_BASE; | |
336 } | |
337 } | |
338 | |
339 // Initialize syncpoint structures for each stream. | |
340 sync = (AVSyncPoint*) av_malloc(s->nb_streams * sizeof(AVSyncPoint)); | |
341 if (!sync) { | |
342 // cannot allocate helper structure | |
343 return -1; | |
344 } | |
345 for (i = 0; i < s->nb_streams; ++i) { | |
346 st = s->streams[i]; | |
347 sp = &sync[i]; | |
348 | |
349 sp->pos_lo = INT64_MAX; | |
350 sp->ts_lo = INT64_MAX; | |
351 sp->pos_hi = INT64_MAX; | |
352 sp->ts_hi = INT64_MAX; | |
353 sp->terminated = 0; | |
354 sp->first_ts = AV_NOPTS_VALUE; | |
355 sp->term_ts = ts_max; | |
356 sp->term_ts_tb = time_base; | |
357 sp->last_pos = pos; | |
358 | |
359 st->cur_dts = AV_NOPTS_VALUE; | |
360 | |
361 if (st->discard < AVDISCARD_ALL) | |
362 ++keyframes_to_find; | |
363 } | |
364 | |
365 if (keyframes_to_find == 0) { | |
366 // No stream active, error. | |
367 av_free(sync); | |
368 return -1; | |
369 } | |
370 | |
371 // Find keyframes in all active streams with timestamp/position just before | |
372 // and just after requested timestamp/position. | |
373 step = 1024; | |
374 curpos = pos; | |
375 for (;;) { | |
376 url_fseek(s->pb, curpos, SEEK_SET); | |
377 search_hi_lo_keyframes(s, | |
378 ts, time_base, | |
379 flags, | |
380 sync, | |
381 keyframes_to_find, | |
382 &found_lo, &found_hi, | |
383 first_iter); | |
384 if (found_lo == keyframes_to_find && found_hi == keyframes_to_find) | |
385 break; // have all keyframes we wanted | |
386 if (curpos == 0) | |
387 break; // cannot go back anymore | |
388 | |
389 curpos = pos - step; | |
390 if (curpos < 0) | |
391 curpos = 0; | |
392 step *= 2; | |
393 | |
394 // switch termination positions | |
395 for (i = 0; i < s->nb_streams; ++i) { | |
396 st = s->streams[i]; | |
397 st->cur_dts = AV_NOPTS_VALUE; | |
398 | |
399 sp = &sync[i]; | |
400 if (sp->first_ts != AV_NOPTS_VALUE) { | |
401 sp->term_ts = sp->first_ts; | |
402 sp->term_ts_tb = sp->first_ts_tb; | |
403 sp->first_ts = AV_NOPTS_VALUE; | |
404 } | |
405 sp->terminated = 0; | |
406 sp->last_pos = curpos; | |
407 } | |
408 first_iter = 0; | |
409 } | |
410 | |
411 // Find actual position to start decoding so that decoder synchronizes | |
412 // closest to ts and between ts_min and ts_max. | |
413 pos = INT64_MAX; | |
414 | |
415 for (i = 0; i < s->nb_streams; ++i) { | |
416 st = s->streams[i]; | |
417 if (st->discard < AVDISCARD_ALL) { | |
418 sp = &sync[i]; | |
419 min_distance = INT64_MAX; | |
420 // Find timestamp closest to requested timestamp within min/max limits. | |
421 if (sp->pos_lo != INT64_MAX | |
422 && compare_ts(ts_min, time_base, sp->ts_lo, st->time_base) <= 0 | |
423 && compare_ts(sp->ts_lo, st->time_base, ts_max, time_base) <= 0) { | |
424 // low timestamp is in range | |
425 min_distance = ts_distance(ts, time_base, sp->ts_lo, st->time_base); | |
426 min_pos = sp->pos_lo; | |
427 } | |
428 if (sp->pos_hi != INT64_MAX | |
429 && compare_ts(ts_min, time_base, sp->ts_hi, st->time_base) <= 0 | |
430 && compare_ts(sp->ts_hi, st->time_base, ts_max, time_base) <= 0) { | |
431 // high timestamp is in range, check distance | |
432 distance = ts_distance(sp->ts_hi, st->time_base, ts, time_base); | |
433 if (distance < min_distance) { | |
434 min_distance = distance; | |
435 min_pos = sp->pos_hi; | |
436 } | |
437 } | |
438 if (min_distance == INT64_MAX) { | |
439 // no timestamp is in range, cannot seek | |
440 av_free(sync); | |
441 return -1; | |
442 } | |
443 if (min_pos < pos) | |
444 pos = min_pos; | |
445 } | |
446 } | |
447 | |
448 url_fseek(s->pb, pos, SEEK_SET); | |
449 av_free(sync); | |
450 return pos; | |
451 } | |
452 | |
453 AVParserState *ff_store_parser_state(AVFormatContext *s) | |
454 { | |
455 int i; | |
456 AVStream *st; | |
457 AVStreamState *ss; | |
458 AVParserState *state = (AVParserState*) av_malloc(sizeof(AVParserState)); | |
459 if (!state) | |
460 return NULL; | |
461 | |
462 state->stream_states = (AVStreamState*) av_malloc(sizeof(AVStreamState) * s->nb_streams); | |
463 if (!state->stream_states) { | |
464 av_free(state); | |
465 return NULL; | |
466 } | |
467 | |
468 state->fpos = url_ftell(s->pb); | |
469 | |
470 // copy context structures | |
471 state->cur_st = s->cur_st; | |
472 state->packet_buffer = s->packet_buffer; | |
473 state->raw_packet_buffer = s->raw_packet_buffer; | |
474 state->raw_packet_buffer_remaining_size = s->raw_packet_buffer_remaining_size; | |
475 | |
476 s->cur_st = NULL; | |
477 s->packet_buffer = NULL; | |
478 s->raw_packet_buffer = NULL; | |
479 s->raw_packet_buffer_remaining_size = RAW_PACKET_BUFFER_SIZE; | |
480 | |
481 // copy stream structures | |
482 state->nb_streams = s->nb_streams; | |
483 for (i = 0; i < s->nb_streams; i++) { | |
484 st = s->streams[i]; | |
485 ss = &state->stream_states[i]; | |
486 | |
487 ss->parser = st->parser; | |
488 ss->last_IP_pts = st->last_IP_pts; | |
489 ss->cur_dts = st->cur_dts; | |
490 ss->reference_dts = st->reference_dts; | |
491 ss->cur_ptr = st->cur_ptr; | |
492 ss->cur_len = st->cur_len; | |
493 ss->probe_packets = st->probe_packets; | |
494 ss->cur_pkt = st->cur_pkt; | |
495 | |
496 st->parser = NULL; | |
497 st->last_IP_pts = AV_NOPTS_VALUE; | |
498 st->cur_dts = AV_NOPTS_VALUE; | |
499 st->reference_dts = AV_NOPTS_VALUE; | |
500 st->cur_ptr = NULL; | |
501 st->cur_len = 0; | |
502 st->probe_packets = MAX_PROBE_PACKETS; | |
503 av_init_packet(&st->cur_pkt); | |
504 } | |
505 | |
506 return state; | |
507 } | |
508 | |
509 void ff_restore_parser_state(AVFormatContext *s, AVParserState *state) | |
510 { | |
511 int i; | |
512 AVStream *st; | |
513 AVStreamState *ss; | |
514 av_read_frame_flush(s); | |
515 | |
516 if (!state) | |
517 return; | |
518 | |
519 url_fseek(s->pb, state->fpos, SEEK_SET); | |
520 | |
521 // copy context structures | |
522 s->cur_st = state->cur_st; | |
523 s->packet_buffer = state->packet_buffer; | |
524 s->raw_packet_buffer = state->raw_packet_buffer; | |
525 s->raw_packet_buffer_remaining_size = state->raw_packet_buffer_remaining_size; | |
526 | |
527 // copy stream structures | |
528 for (i = 0; i < state->nb_streams; i++) { | |
529 st = s->streams[i]; | |
530 ss = &state->stream_states[i]; | |
531 | |
532 st->parser = ss->parser; | |
533 st->last_IP_pts = ss->last_IP_pts; | |
534 st->cur_dts = ss->cur_dts; | |
535 st->reference_dts = ss->reference_dts; | |
536 st->cur_ptr = ss->cur_ptr; | |
537 st->cur_len = ss->cur_len; | |
538 st->probe_packets = ss->probe_packets; | |
539 st->cur_pkt = ss->cur_pkt; | |
540 } | |
541 | |
542 av_free(state->stream_states); | |
543 av_free(state); | |
544 } | |
545 | |
546 static void free_packet_list(AVPacketList *pktl) | |
547 { | |
548 AVPacketList *cur; | |
549 while (pktl) { | |
550 cur = pktl; | |
551 pktl = cur->next; | |
552 av_free_packet(&cur->pkt); | |
553 av_free(cur); | |
554 } | |
555 } | |
556 | |
557 void ff_free_parser_state(AVFormatContext *s, AVParserState *state) | |
558 { | |
559 int i; | |
560 AVStreamState *ss; | |
561 | |
562 if (!state) | |
563 return; | |
564 | |
565 for (i = 0; i < state->nb_streams; i++) { | |
566 ss = &state->stream_states[i]; | |
567 if (ss->parser) | |
568 av_parser_close(ss->parser); | |
569 av_free_packet(&ss->cur_pkt); | |
570 } | |
571 | |
572 free_packet_list(state->packet_buffer); | |
573 free_packet_list(state->raw_packet_buffer); | |
574 | |
575 av_free(state->stream_states); | |
576 av_free(state); | |
577 } | |
578 |