Statistics
| Branch: | Revision:

ffmpeg / libavformat / seek.c @ f59d8ff8

History | View | Annotate | Download (17.7 KB)

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