2 * Utility functions for seeking for use within FFmpeg 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 to store parser state of AVStream.
33 typedef struct AVStreamState
{
34 // Saved members of AVStream
35 AVCodecParserContext
*parser
;
39 int64_t reference_dts
;
40 const uint8_t *cur_ptr
;
46 * Helper structure to store parser state of AVFormat.
48 struct AVParserState
{
49 int64_t fpos
; ///< File position at the time of call.
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.
57 // Saved info for streams.
58 int nb_streams
; ///< Number of streams with stored state.
59 AVStreamState
*stream_states
; ///< States of individual streams (array).
63 * Helper structure describing keyframe search state of one stream.
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.
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.
72 int64_t last_pos
; ///< Last known position of a frame, for multi-frame packets.
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.
79 int terminated
; ///< Termination flag for current iteration.
83 * Compare two timestamps exactly, taking into account their respective time bases.
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.
91 static int compare_ts(int64_t ts_a
, AVRational tb_a
, int64_t ts_b
, AVRational tb_b
)
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;
104 a
= ts_a
* tb_a
.num
* tb_b
.den
;
105 b
= ts_b
* tb_b
.num
* tb_a
.den
;
111 return (res
>> 63) | 1;
115 * Compute a distance between timestamps.
117 * Distances are only comparable, if same time bases are used for computing
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.
126 static int64_t ts_distance(int64_t ts_hi
, AVRational tb_hi
, int64_t ts_lo
, AVRational tb_lo
)
130 hi
= ts_hi
* tb_hi
.num
* tb_lo
.den
;
131 lo
= ts_lo
* tb_lo
.num
* tb_hi
.den
;
137 * Partial search for keyframes in multiple streams.
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).
144 * This routine is called iteratively with exponential backoff to find lower
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.
157 static void search_hi_lo_keyframes(AVFormatContext
*s
,
162 int keyframes_to_find
,
172 int terminated_count
= 0;
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
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
) {
184 if (sp
->pos_hi
== INT64_MAX
) {
185 // No high frame exists for this stream
187 sp
->ts_hi
= INT64_MAX
;
188 sp
->pos_hi
= INT64_MAX
- 1;
195 idx
= pkt
.stream_index
;
196 st
= s
->streams
[idx
];
197 if (st
->discard
>= AVDISCARD_ALL
) {
198 // This stream is not active, skip packet.
207 if (pts
== AV_NOPTS_VALUE
) {
208 // Some formats don't provide PTS, only DTS.
211 av_free_packet(&pkt
);
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).
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.
233 // Get stream time_base.
235 ts_tb
= st
->time_base
;
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).
244 sp
->first_ts_tb
= ts_tb
;
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
) {
252 if (sp
->pos_hi
== INT64_MAX
) {
253 // No high frame exists for this stream
255 sp
->ts_hi
= INT64_MAX
;
256 sp
->pos_hi
= INT64_MAX
- 1;
258 if (terminated_count
== keyframes_to_find
)
259 break; // all terminated, iteration done
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.
271 } else if (sp
->ts_lo
< ts
) {
272 // Found a better match (closer to target timestamp).
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.
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).
290 } else if (sp
->ts_hi
> ts
) {
291 // Found a better match (actually, shouldn't happen).
299 // Clean up the parser.
300 av_read_frame_flush(s
);
303 int64_t ff_gen_syncpoint_search(AVFormatContext
*s
,
311 AVSyncPoint
*sync
, *sp
;
314 int keyframes_to_find
= 0;
317 int found_lo
= 0, found_hi
= 0;
318 int64_t min_distance
, distance
;
321 AVRational time_base
;
323 if (flags
& AVSEEK_FLAG_BYTE
) {
324 /* For byte seeking, we have exact 1:1 "timestamps" - positions */
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
;
333 /* No reference stream, use AV_TIME_BASE as reference time base */
335 time_base
.den
= AV_TIME_BASE
;
339 // Initialize syncpoint structures for each stream.
340 sync
= (AVSyncPoint
*) av_malloc(s
->nb_streams
* sizeof(AVSyncPoint
));
342 // cannot allocate helper structure
345 for (i
= 0; i
< s
->nb_streams
; ++i
) {
349 sp
->pos_lo
= INT64_MAX
;
350 sp
->ts_lo
= INT64_MAX
;
351 sp
->pos_hi
= INT64_MAX
;
352 sp
->ts_hi
= INT64_MAX
;
354 sp
->first_ts
= AV_NOPTS_VALUE
;
355 sp
->term_ts
= ts_max
;
356 sp
->term_ts_tb
= time_base
;
359 st
->cur_dts
= AV_NOPTS_VALUE
;
361 if (st
->discard
< AVDISCARD_ALL
)
365 if (keyframes_to_find
== 0) {
366 // No stream active, error.
371 // Find keyframes in all active streams with timestamp/position just before
372 // and just after requested timestamp/position.
376 url_fseek(s
->pb
, curpos
, SEEK_SET
);
377 search_hi_lo_keyframes(s
,
382 &found_lo
, &found_hi
,
384 if (found_lo
== keyframes_to_find
&& found_hi
== keyframes_to_find
)
385 break; // have all keyframes we wanted
387 break; // cannot go back anymore
394 // switch termination positions
395 for (i
= 0; i
< s
->nb_streams
; ++i
) {
397 st
->cur_dts
= AV_NOPTS_VALUE
;
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
;
406 sp
->last_pos
= curpos
;
411 // Find actual position to start decoding so that decoder synchronizes
412 // closest to ts and between ts_min and ts_max.
415 for (i
= 0; i
< s
->nb_streams
; ++i
) {
417 if (st
->discard
< AVDISCARD_ALL
) {
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
;
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
;
438 if (min_distance
== INT64_MAX
) {
439 // no timestamp is in range, cannot seek
448 url_fseek(s
->pb
, pos
, SEEK_SET
);
453 AVParserState
*ff_store_parser_state(AVFormatContext
*s
)
458 AVParserState
*state
= (AVParserState
*) av_malloc(sizeof(AVParserState
));
462 state
->stream_states
= (AVStreamState
*) av_malloc(sizeof(AVStreamState
) * s
->nb_streams
);
463 if (!state
->stream_states
) {
468 state
->fpos
= url_ftell(s
->pb
);
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
;
477 s
->packet_buffer
= NULL
;
478 s
->raw_packet_buffer
= NULL
;
479 s
->raw_packet_buffer_remaining_size
= RAW_PACKET_BUFFER_SIZE
;
481 // copy stream structures
482 state
->nb_streams
= s
->nb_streams
;
483 for (i
= 0; i
< s
->nb_streams
; i
++) {
485 ss
= &state
->stream_states
[i
];
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
;
497 st
->last_IP_pts
= AV_NOPTS_VALUE
;
498 st
->cur_dts
= AV_NOPTS_VALUE
;
499 st
->reference_dts
= AV_NOPTS_VALUE
;
502 st
->probe_packets
= MAX_PROBE_PACKETS
;
503 av_init_packet(&st
->cur_pkt
);
509 void ff_restore_parser_state(AVFormatContext
*s
, AVParserState
*state
)
514 av_read_frame_flush(s
);
519 url_fseek(s
->pb
, state
->fpos
, SEEK_SET
);
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
;
527 // copy stream structures
528 for (i
= 0; i
< state
->nb_streams
; i
++) {
530 ss
= &state
->stream_states
[i
];
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
;
542 av_free(state
->stream_states
);
546 static void free_packet_list(AVPacketList
*pktl
)
552 av_free_packet(&cur
->pkt
);
557 void ff_free_parser_state(AVFormatContext
*s
, AVParserState
*state
)
565 for (i
= 0; i
< state
->nb_streams
; i
++) {
566 ss
= &state
->stream_states
[i
];
568 av_parser_close(ss
->parser
);
569 av_free_packet(&ss
->cur_pkt
);
572 free_packet_list(state
->packet_buffer
);
573 free_packet_list(state
->raw_packet_buffer
);
575 av_free(state
->stream_states
);