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