path: root/libavformat/seek.c (plain)
blob: 0ae99eb211afb562194efb5df9c754ebc336c007

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->reference_dts = st->reference_dts;
432	ss->probe_packets = st->probe_packets;
433
434	st->parser = NULL;
435	st->last_IP_pts = AV_NOPTS_VALUE;
436	st->cur_dts = AV_NOPTS_VALUE;
437	st->reference_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->reference_dts = ss->reference_dts;
471	st->probe_packets = ss->probe_packets;
472	}
473
474	av_free(state->stream_states);
475	av_free(state);
476	}
477
478	static void free_packet_list(AVPacketList *pktl)
479	{
480	AVPacketList *cur;
481	while (pktl) {
482	cur = pktl;
483	pktl = cur->next;
484	av_free_packet(&cur->pkt);
485	av_free(cur);
486	}
487	}
488
489	void ff_free_parser_state(AVFormatContext *s, AVParserState *state)
490	{
491	int i;
492	AVParserStreamState *ss;
493
494	if (!state)
495	return;
496
497	for (i = 0; i < state->nb_streams; i++) {
498	ss = &state->stream_states[i];
499	if (ss->parser)
500	av_parser_close(ss->parser);
501	}
502
503	free_packet_list(state->packet_buffer);
504	free_packet_list(state->parse_queue);
505	free_packet_list(state->raw_packet_buffer);
506
507	av_free(state->stream_states);
508	av_free(state);
509	}
510