2 * seek utility functions for use within format handlers
4 * Copyright (c) 2009 Ivan Schreter
6 * This file is part of FFmpeg.
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.
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.
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
24 #include "libavutil/mem.h"
26 // NOTE: implementation should be moved here in another patch, to keep patches
28 extern void av_read_frame_flush(AVFormatContext
*s
);
31 * helper structure describing keyframe search state of one stream
34 int64_t pos_lo
; ///< position of the frame with low timestamp in file or INT64_MAX if not found (yet)
35 int64_t ts_lo
; ///< frame presentation timestamp or same as pos_lo for byte seeking
37 int64_t pos_hi
; ///< position of the frame with high timestamp in file or INT64_MAX if not found (yet)
38 int64_t ts_hi
; ///< frame presentation timestamp or same as pos_hi for byte seeking
40 int64_t last_pos
; ///< last known position of a frame, for multi-frame packets
42 int64_t term_ts
; ///< termination timestamp (which TS we already read)
43 AVRational term_ts_tb
; ///< timebase for term_ts
44 int64_t first_ts
; ///< first packet timestamp in this iteration (to fill term_ts later)
45 AVRational first_ts_tb
; ///< timebase for first_ts
47 int terminated
; ///< termination flag for the current iteration
51 * Compare two timestamps exactly, taking their respective time bases into account.
53 * @param ts_a timestamp A
54 * @param tb_a time base for timestamp A
55 * @param ts_b timestamp B
56 * @param tb_b time base for timestamp A
57 * @return -1, 0 or 1 if timestamp A is less than, equal or greater than timestamp B
59 static int compare_ts(int64_t ts_a
, AVRational tb_a
, int64_t ts_b
, AVRational tb_b
)
63 if (ts_a
== INT64_MIN
)
64 return ts_a
< ts_b
? -1 : 0;
65 if (ts_a
== INT64_MAX
)
66 return ts_a
> ts_b
? 1 : 0;
67 if (ts_b
== INT64_MIN
)
68 return ts_a
> ts_b
? 1 : 0;
69 if (ts_b
== INT64_MAX
)
70 return ts_a
< ts_b
? -1 : 0;
72 a
= ts_a
* tb_a
.num
* tb_b
.den
;
73 b
= ts_b
* tb_b
.num
* tb_a
.den
;
79 return (res
>> 63) | 1;
83 * Compute a distance between timestamps.
85 * Distances are only comparable, if same time bases are used for computing
88 * @param ts_hi high timestamp
89 * @param tb_hi high timestamp time base
90 * @param ts_lo low timestamp
91 * @param tb_lo low timestamp time base
92 * @return representation of distance between high and low timestamps
94 static int64_t ts_distance(int64_t ts_hi
,
101 hi
= ts_hi
* tb_hi
.num
* tb_lo
.den
;
102 lo
= ts_lo
* tb_lo
.num
* tb_hi
.den
;
108 * Partial search for keyframes in multiple streams.
110 * This routine searches in each stream for the next lower and the next higher
111 * timestamp compared to the given target timestamp. The search starts at the current
112 * file position and ends at the file position, where all streams have already been
113 * examined (or when all higher key frames are found in the first iteration).
115 * This routine is called iteratively with an exponential backoff to find the lower
118 * @param s format context
119 * @param timestamp target timestamp (or position, if AVSEEK_FLAG_BYTE)
120 * @param timebase time base for timestamps
121 * @param flags seeking flags
122 * @param sync array with information per stream
123 * @param keyframes_to_find count of keyframes to find in total
124 * @param found_lo ptr to the count of already found low timestamp keyframes
125 * @param found_hi ptr to the count of already found high timestamp keyframes
126 * @param first_iter flag for first iteration
128 static void search_hi_lo_keyframes(AVFormatContext
*s
,
133 int keyframes_to_find
,
143 int terminated_count
= 0;
145 int64_t pts
, dts
; // PTS/DTS from stream
146 int64_t ts
; // PTS in stream-local time base or position for byte seeking
147 AVRational ts_tb
; // Time base of the stream or 1:1 for byte seeking
150 if (av_read_frame(s
, &pkt
) < 0) {
151 // EOF or error, make sure high flags are set
152 for (idx
= 0; idx
< s
->nb_streams
; ++idx
) {
153 if (s
->streams
[idx
]->discard
< AVDISCARD_ALL
) {
155 if (sp
->pos_hi
== INT64_MAX
) {
156 // no high frame exists for this stream
158 sp
->ts_hi
= INT64_MAX
;
159 sp
->pos_hi
= INT64_MAX
- 1;
166 idx
= pkt
.stream_index
;
167 st
= s
->streams
[idx
];
168 if (st
->discard
>= AVDISCARD_ALL
)
169 // this stream is not active, skip packet
178 if (pts
== AV_NOPTS_VALUE
)
179 // some formats don't provide PTS, only DTS
182 av_free_packet(&pkt
);
184 // Multi-frame packets only return position for the very first frame.
185 // Other frames are read with position == -1. Therefore, we note down
186 // last known position of a frame and use it if a frame without
187 // position arrives. In this way, it's possible to seek to proper
188 // position. Additionally, for parsers not providing position at all,
189 // an approximation will be used (starting position of this iteration).
195 // Evaluate key frames with known TS (or any frames, if AVSEEK_FLAG_ANY set).
196 if (pts
!= AV_NOPTS_VALUE
&&
197 ((flg
& PKT_FLAG_KEY
) || (flags
& AVSEEK_FLAG_ANY
))) {
198 if (flags
& AVSEEK_FLAG_BYTE
) {
199 // for byte seeking, use position as timestamp
204 // otherwise, get stream time_base
206 ts_tb
= st
->time_base
;
209 if (sp
->first_ts
== AV_NOPTS_VALUE
) {
210 // Note down termination timestamp for the next iteration - when
211 // we encounter a packet with the same timestamp, we will ignore
212 // any further packets for this stream in next iteration (as they
213 // are already evaluated).
215 sp
->first_ts_tb
= ts_tb
;
218 if (sp
->term_ts
!= AV_NOPTS_VALUE
&&
219 compare_ts(ts
, ts_tb
, sp
->term_ts
, sp
->term_ts_tb
) > 0) {
220 // past the end position from last iteration, ignore packet
221 if (!sp
->terminated
) {
224 if (sp
->pos_hi
== INT64_MAX
) {
225 // no high frame exists for this stream
227 sp
->ts_hi
= INT64_MAX
;
228 sp
->pos_hi
= INT64_MAX
- 1;
230 if (terminated_count
== keyframes_to_find
)
231 break; // all terminated, iteration done
236 if (compare_ts(ts
, ts_tb
, timestamp
, timebase
) <= 0) {
237 // keyframe found before target timestamp
238 if (sp
->pos_lo
== INT64_MAX
) {
239 // found first keyframe lower than target timestamp
243 } else if (sp
->ts_lo
< ts
) {
244 // found a better match (closer to target timestamp)
249 if (compare_ts(ts
, ts_tb
, timestamp
, timebase
) >= 0) {
250 // keyframe found after target timestamp
251 if (sp
->pos_hi
== INT64_MAX
) {
252 // found first keyframe higher than target timestamp
256 if (*found_hi
>= keyframes_to_find
&& first_iter
) {
257 // We found high frame for all. They may get updated
258 // to TS closer to target TS in later iterations (which
259 // will stop at start position of previous iteration).
262 } else if (sp
->ts_hi
> ts
) {
263 // found a better match (actually, shouldn't happen)
271 // Clean up the parser.
272 av_read_frame_flush(s
);
275 int64_t ff_gen_syncpoint_search(AVFormatContext
*s
,
283 AVSyncPoint
*sync
, *sp
;
286 int keyframes_to_find
= 0;
289 int found_lo
= 0, found_hi
= 0;
290 int64_t min_distance
, distance
;
293 AVRational time_base
;
295 if (flags
& AVSEEK_FLAG_BYTE
) {
296 // for byte seeking, we have exact 1:1 "timestamps" - positions
300 if (stream_index
>= 0) {
301 // we have a reference stream, which time base we use
302 st
= s
->streams
[stream_index
];
303 time_base
= st
->time_base
;
305 // no reference stream, use AV_TIME_BASE as reference time base
307 time_base
.den
= AV_TIME_BASE
;
311 // Initialize syncpoint structures for each stream.
312 sync
= av_malloc(s
->nb_streams
* sizeof(AVSyncPoint
));
314 // cannot allocate helper structure
317 for (i
= 0; i
< s
->nb_streams
; ++i
) {
321 sp
->pos_lo
= INT64_MAX
;
322 sp
->ts_lo
= INT64_MAX
;
323 sp
->pos_hi
= INT64_MAX
;
324 sp
->ts_hi
= INT64_MAX
;
326 sp
->first_ts
= AV_NOPTS_VALUE
;
327 sp
->term_ts
= ts_max
;
328 sp
->term_ts_tb
= time_base
;
331 st
->cur_dts
= AV_NOPTS_VALUE
;
333 if (st
->discard
< AVDISCARD_ALL
)
337 if (!keyframes_to_find
) {
338 // no stream active, error
343 // Find keyframes in all active streams with timestamp/position just before
344 // and just after requested timestamp/position.
345 step
= s
->pb
->buffer_size
;
346 curpos
= FFMAX(pos
- step
/ 2, 0);
348 url_fseek(s
->pb
, curpos
, SEEK_SET
);
349 search_hi_lo_keyframes(s
,
354 &found_lo
, &found_hi
,
356 if (found_lo
== keyframes_to_find
&& found_hi
== keyframes_to_find
)
357 break; // have all keyframes we wanted
359 break; // cannot go back anymore
366 // switch termination positions
367 for (i
= 0; i
< s
->nb_streams
; ++i
) {
369 st
->cur_dts
= AV_NOPTS_VALUE
;
372 if (sp
->first_ts
!= AV_NOPTS_VALUE
) {
373 sp
->term_ts
= sp
->first_ts
;
374 sp
->term_ts_tb
= sp
->first_ts_tb
;
375 sp
->first_ts
= AV_NOPTS_VALUE
;
378 sp
->last_pos
= curpos
;
383 // Find actual position to start decoding so that decoder synchronizes
384 // closest to ts and between ts_min and ts_max.
387 for (i
= 0; i
< s
->nb_streams
; ++i
) {
389 if (st
->discard
< AVDISCARD_ALL
) {
391 min_distance
= INT64_MAX
;
392 // Find timestamp closest to requested timestamp within min/max limits.
393 if (sp
->pos_lo
!= INT64_MAX
394 && compare_ts(ts_min
, time_base
, sp
->ts_lo
, st
->time_base
) <= 0
395 && compare_ts(sp
->ts_lo
, st
->time_base
, ts_max
, time_base
) <= 0) {
396 // low timestamp is in range
397 min_distance
= ts_distance(ts
, time_base
, sp
->ts_lo
, st
->time_base
);
398 min_pos
= sp
->pos_lo
;
400 if (sp
->pos_hi
!= INT64_MAX
401 && compare_ts(ts_min
, time_base
, sp
->ts_hi
, st
->time_base
) <= 0
402 && compare_ts(sp
->ts_hi
, st
->time_base
, ts_max
, time_base
) <= 0) {
403 // high timestamp is in range, check distance
404 distance
= ts_distance(sp
->ts_hi
, st
->time_base
, ts
, time_base
);
405 if (distance
< min_distance
) {
406 min_distance
= distance
;
407 min_pos
= sp
->pos_hi
;
410 if (min_distance
== INT64_MAX
) {
411 // no timestamp is in range, cannot seek
420 url_fseek(s
->pb
, pos
, SEEK_SET
);
425 AVParserState
*ff_store_parser_state(AVFormatContext
*s
)
429 AVParserStreamState
*ss
;
430 AVParserState
*state
= av_malloc(sizeof(AVParserState
));
434 state
->stream_states
= av_malloc(sizeof(AVParserStreamState
) * s
->nb_streams
);
435 if (!state
->stream_states
) {
440 state
->fpos
= url_ftell(s
->pb
);
442 // copy context structures
443 state
->cur_st
= s
->cur_st
;
444 state
->packet_buffer
= s
->packet_buffer
;
445 state
->raw_packet_buffer
= s
->raw_packet_buffer
;
446 state
->raw_packet_buffer_remaining_size
= s
->raw_packet_buffer_remaining_size
;
449 s
->packet_buffer
= NULL
;
450 s
->raw_packet_buffer
= NULL
;
451 s
->raw_packet_buffer_remaining_size
= RAW_PACKET_BUFFER_SIZE
;
453 // copy stream structures
454 state
->nb_streams
= s
->nb_streams
;
455 for (i
= 0; i
< s
->nb_streams
; i
++) {
457 ss
= &state
->stream_states
[i
];
459 ss
->parser
= st
->parser
;
460 ss
->last_IP_pts
= st
->last_IP_pts
;
461 ss
->cur_dts
= st
->cur_dts
;
462 ss
->reference_dts
= st
->reference_dts
;
463 ss
->cur_ptr
= st
->cur_ptr
;
464 ss
->cur_len
= st
->cur_len
;
465 ss
->probe_packets
= st
->probe_packets
;
466 ss
->cur_pkt
= st
->cur_pkt
;
469 st
->last_IP_pts
= AV_NOPTS_VALUE
;
470 st
->cur_dts
= AV_NOPTS_VALUE
;
471 st
->reference_dts
= AV_NOPTS_VALUE
;
474 st
->probe_packets
= MAX_PROBE_PACKETS
;
475 av_init_packet(&st
->cur_pkt
);
481 void ff_restore_parser_state(AVFormatContext
*s
, AVParserState
*state
)
485 AVParserStreamState
*ss
;
486 av_read_frame_flush(s
);
491 url_fseek(s
->pb
, state
->fpos
, SEEK_SET
);
493 // copy context structures
494 s
->cur_st
= state
->cur_st
;
495 s
->packet_buffer
= state
->packet_buffer
;
496 s
->raw_packet_buffer
= state
->raw_packet_buffer
;
497 s
->raw_packet_buffer_remaining_size
= state
->raw_packet_buffer_remaining_size
;
499 // copy stream structures
500 for (i
= 0; i
< state
->nb_streams
; i
++) {
502 ss
= &state
->stream_states
[i
];
504 st
->parser
= ss
->parser
;
505 st
->last_IP_pts
= ss
->last_IP_pts
;
506 st
->cur_dts
= ss
->cur_dts
;
507 st
->reference_dts
= ss
->reference_dts
;
508 st
->cur_ptr
= ss
->cur_ptr
;
509 st
->cur_len
= ss
->cur_len
;
510 st
->probe_packets
= ss
->probe_packets
;
511 st
->cur_pkt
= ss
->cur_pkt
;
514 av_free(state
->stream_states
);
518 static void free_packet_list(AVPacketList
*pktl
)
524 av_free_packet(&cur
->pkt
);
529 void ff_free_parser_state(AVFormatContext
*s
, AVParserState
*state
)
532 AVParserStreamState
*ss
;
537 for (i
= 0; i
< state
->nb_streams
; i
++) {
538 ss
= &state
->stream_states
[i
];
540 av_parser_close(ss
->parser
);
541 av_free_packet(&ss
->cur_pkt
);
544 free_packet_list(state
->packet_buffer
);
545 free_packet_list(state
->raw_packet_buffer
);
547 av_free(state
->stream_states
);