WebVTT demuxer and decoder.
[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/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 }