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 "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  */
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.
242 }
243 
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);
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 
395 {
396  int i;
397  AVStream *st;
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;
416 
417  s->packet_buffer = NULL;
418  s->parse_queue = NULL;
419  s->raw_packet_buffer = NULL;
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;
436  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->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 
490 {
491  int i;
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 
506 
507  av_free(state->stream_states);
508  av_free(state);
509 }