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