Use I/O buffer size as initial value for backoff for seeking sync point search.
[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
26 // NOTE: implementation should be moved here in another patch, to keep patches
27 // separated.
28 extern void av_read_frame_flush(AVFormatContext *s);
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  * Compare two timestamps exactly, taking their respective time bases into account.
52  *
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
58  */
59 static int compare_ts(int64_t ts_a, AVRational tb_a, int64_t ts_b, AVRational tb_b)
60 {
61     int64_t a, b, res;
62
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;
71
72     a = ts_a * tb_a.num * tb_b.den;
73     b = ts_b * tb_b.num * tb_a.den;
74
75     res = a - b;
76     if (!res)
77         return 0;
78     else
79         return (res >> 63) | 1;
80 }
81
82 /**
83  * Compute a distance between timestamps.
84  *
85  * Distances are only comparable, if same time bases are used for computing
86  * distances.
87  *
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
93  */
94 static int64_t ts_distance(int64_t ts_hi,
95                            AVRational tb_hi,
96                            int64_t ts_lo,
97                            AVRational tb_lo)
98 {
99     int64_t hi, lo;
100
101     hi = ts_hi * tb_hi.num * tb_lo.den;
102     lo = ts_lo * tb_lo.num * tb_hi.den;
103
104     return hi - lo;
105 }
106
107 /**
108  * Partial search for keyframes in multiple streams.
109  *
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).
114  *
115  * This routine is called iteratively with an exponential backoff to find the lower
116  * timestamp.
117  *
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
127  */
128 static void search_hi_lo_keyframes(AVFormatContext *s,
129                                    int64_t timestamp,
130                                    AVRational timebase,
131                                    int flags,
132                                    AVSyncPoint *sync,
133                                    int keyframes_to_find,
134                                    int *found_lo,
135                                    int *found_hi,
136                                    int first_iter)
137 {
138     AVPacket pkt;
139     AVSyncPoint *sp;
140     AVStream *st;
141     int idx;
142     int flg;
143     int terminated_count = 0;
144     int64_t pos;
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
148
149     for (;;) {
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) {
154                     sp = &sync[idx];
155                     if (sp->pos_hi == INT64_MAX) {
156                         // no high frame exists for this stream
157                         (*found_hi)++;
158                         sp->ts_hi  = INT64_MAX;
159                         sp->pos_hi = INT64_MAX - 1;
160                     }
161                 }
162             }
163             break;
164         }
165
166         idx = pkt.stream_index;
167         st = s->streams[idx];
168         if (st->discard >= AVDISCARD_ALL)
169             // this stream is not active, skip packet
170             continue;
171
172         sp = &sync[idx];
173
174         flg = pkt.flags;
175         pos = pkt.pos;
176         pts = pkt.pts;
177         dts = pkt.dts;
178         if (pts == AV_NOPTS_VALUE)
179             // some formats don't provide PTS, only DTS
180             pts = dts;
181
182         av_free_packet(&pkt);
183
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).
190         if (pos < 0)
191             pos = sp->last_pos;
192         else
193             sp->last_pos = pos;
194
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
200                 ts        = pos;
201                 ts_tb.num = 1;
202                 ts_tb.den = 1;
203             } else {
204                 // otherwise, get stream time_base
205                 ts    = pts;
206                 ts_tb = st->time_base;
207             }
208
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).
214                 sp->first_ts    = ts;
215                 sp->first_ts_tb = ts_tb;
216             }
217
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) {
222                     sp->terminated = 1;
223                     ++terminated_count;
224                     if (sp->pos_hi == INT64_MAX) {
225                         // no high frame exists for this stream
226                         (*found_hi)++;
227                         sp->ts_hi  = INT64_MAX;
228                         sp->pos_hi = INT64_MAX - 1;
229                     }
230                     if (terminated_count == keyframes_to_find)
231                         break;  // all terminated, iteration done
232                 }
233                 continue;
234             }
235
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
240                     (*found_lo)++;
241                     sp->ts_lo  = ts;
242                     sp->pos_lo = pos;
243                 } else if (sp->ts_lo < ts) {
244                     // found a better match (closer to target timestamp)
245                     sp->ts_lo  = ts;
246                     sp->pos_lo = pos;
247                 }
248             }
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
253                     (*found_hi)++;
254                     sp->ts_hi  = ts;
255                     sp->pos_hi = pos;
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).
260                         break;
261                     }
262                 } else if (sp->ts_hi > ts) {
263                     // found a better match (actually, shouldn't happen)
264                     sp->ts_hi  = ts;
265                     sp->pos_hi = pos;
266                 }
267             }
268         }
269     }
270
271     // Clean up the parser.
272     av_read_frame_flush(s);
273 }
274
275 int64_t ff_gen_syncpoint_search(AVFormatContext *s,
276                                 int stream_index,
277                                 int64_t pos,
278                                 int64_t ts_min,
279                                 int64_t ts,
280                                 int64_t ts_max,
281                                 int flags)
282 {
283     AVSyncPoint *sync, *sp;
284     AVStream *st;
285     int i;
286     int keyframes_to_find = 0;
287     int64_t curpos;
288     int64_t step;
289     int found_lo = 0, found_hi = 0;
290     int64_t min_distance, distance;
291     int64_t min_pos = 0;
292     int first_iter = 1;
293     AVRational time_base;
294
295     if (flags & AVSEEK_FLAG_BYTE) {
296         // for byte seeking, we have exact 1:1 "timestamps" - positions
297         time_base.num = 1;
298         time_base.den = 1;
299     } else {
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;
304         } else {
305             // no reference stream, use AV_TIME_BASE as reference time base
306             time_base.num = 1;
307             time_base.den = AV_TIME_BASE;
308         }
309     }
310
311     // Initialize syncpoint structures for each stream.
312     sync = av_malloc(s->nb_streams * sizeof(AVSyncPoint));
313     if (!sync)
314         // cannot allocate helper structure
315         return -1;
316
317     for (i = 0; i < s->nb_streams; ++i) {
318         st = s->streams[i];
319         sp = &sync[i];
320
321         sp->pos_lo     = INT64_MAX;
322         sp->ts_lo      = INT64_MAX;
323         sp->pos_hi     = INT64_MAX;
324         sp->ts_hi      = INT64_MAX;
325         sp->terminated = 0;
326         sp->first_ts   = AV_NOPTS_VALUE;
327         sp->term_ts    = ts_max;
328         sp->term_ts_tb = time_base;
329         sp->last_pos   = pos;
330
331         st->cur_dts    = AV_NOPTS_VALUE;
332
333         if (st->discard < AVDISCARD_ALL)
334             ++keyframes_to_find;
335     }
336
337     if (!keyframes_to_find) {
338         // no stream active, error
339         av_free(sync);
340         return -1;
341     }
342
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);
347     for (;;) {
348         url_fseek(s->pb, curpos, SEEK_SET);
349         search_hi_lo_keyframes(s,
350                                ts, time_base,
351                                flags,
352                                sync,
353                                keyframes_to_find,
354                                &found_lo, &found_hi,
355                                first_iter);
356         if (found_lo == keyframes_to_find && found_hi == keyframes_to_find)
357             break;  // have all keyframes we wanted
358         if (!curpos)
359             break;  // cannot go back anymore
360
361         curpos = pos - step;
362         if (curpos < 0)
363             curpos = 0;
364         step *= 2;
365
366         // switch termination positions
367         for (i = 0; i < s->nb_streams; ++i) {
368             st = s->streams[i];
369             st->cur_dts = AV_NOPTS_VALUE;
370
371             sp = &sync[i];
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;
376             }
377             sp->terminated = 0;
378             sp->last_pos = curpos;
379         }
380         first_iter = 0;
381     }
382
383     // Find actual position to start decoding so that decoder synchronizes
384     // closest to ts and between ts_min and ts_max.
385     pos = INT64_MAX;
386
387     for (i = 0; i < s->nb_streams; ++i) {
388         st = s->streams[i];
389         if (st->discard < AVDISCARD_ALL) {
390             sp = &sync[i];
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;
399             }
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;
408                 }
409             }
410             if (min_distance == INT64_MAX) {
411                 // no timestamp is in range, cannot seek
412                 av_free(sync);
413                 return -1;
414             }
415             if (min_pos < pos)
416                 pos = min_pos;
417         }
418     }
419
420     url_fseek(s->pb, pos, SEEK_SET);
421     av_free(sync);
422     return pos;
423 }
424
425 AVParserState *ff_store_parser_state(AVFormatContext *s)
426 {
427     int i;
428     AVStream *st;
429     AVParserStreamState *ss;
430     AVParserState *state = av_malloc(sizeof(AVParserState));
431     if (!state)
432         return NULL;
433
434     state->stream_states = av_malloc(sizeof(AVParserStreamState) * s->nb_streams);
435     if (!state->stream_states) {
436         av_free(state);
437         return NULL;
438     }
439
440     state->fpos = url_ftell(s->pb);
441
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;
447
448     s->cur_st                               = NULL;
449     s->packet_buffer                        = NULL;
450     s->raw_packet_buffer                    = NULL;
451     s->raw_packet_buffer_remaining_size     = RAW_PACKET_BUFFER_SIZE;
452
453     // copy stream structures
454     state->nb_streams = s->nb_streams;
455     for (i = 0; i < s->nb_streams; i++) {
456         st = s->streams[i];
457         ss = &state->stream_states[i];
458
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;
467
468         st->parser        = NULL;
469         st->last_IP_pts   = AV_NOPTS_VALUE;
470         st->cur_dts       = AV_NOPTS_VALUE;
471         st->reference_dts = AV_NOPTS_VALUE;
472         st->cur_ptr       = NULL;
473         st->cur_len       = 0;
474         st->probe_packets = MAX_PROBE_PACKETS;
475         av_init_packet(&st->cur_pkt);
476     }
477
478     return state;
479 }
480
481 void ff_restore_parser_state(AVFormatContext *s, AVParserState *state)
482 {
483     int i;
484     AVStream *st;
485     AVParserStreamState *ss;
486     av_read_frame_flush(s);
487
488     if (!state)
489         return;
490
491     url_fseek(s->pb, state->fpos, SEEK_SET);
492
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;
498
499     // copy stream structures
500     for (i = 0; i < state->nb_streams; i++) {
501         st = s->streams[i];
502         ss = &state->stream_states[i];
503
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;
512     }
513
514     av_free(state->stream_states);
515     av_free(state);
516 }
517
518 static void free_packet_list(AVPacketList *pktl)
519 {
520     AVPacketList *cur;
521     while (pktl) {
522         cur = pktl;
523         pktl = cur->next;
524         av_free_packet(&cur->pkt);
525         av_free(cur);
526     }
527 }
528
529 void ff_free_parser_state(AVFormatContext *s, AVParserState *state)
530 {
531     int i;
532     AVParserStreamState *ss;
533
534     if (!state)
535         return;
536
537     for (i = 0; i < state->nb_streams; i++) {
538         ss = &state->stream_states[i];
539         if (ss->parser)
540             av_parser_close(ss->parser);
541         av_free_packet(&ss->cur_pkt);
542     }
543
544     free_packet_list(state->packet_buffer);
545     free_packet_list(state->raw_packet_buffer);
546
547     av_free(state->stream_states);
548     av_free(state);
549 }
550