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