Statistics
| Branch: | Revision:

ffmpeg / libavformat / seek.c @ e16c73e6

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

    
26
// NOTE: implementation should be moved here in another patch, to keep patches
27
// separated.
28

    
29
/**
30
 * helper structure describing keyframe search state of one stream
31
 */
32
typedef struct {
33
    int64_t     pos_lo;      ///< position of the frame with low timestamp in file or INT64_MAX if not found (yet)
34
    int64_t     ts_lo;       ///< frame presentation timestamp or same as pos_lo for byte seeking
35

    
36
    int64_t     pos_hi;      ///< position of the frame with high timestamp in file or INT64_MAX if not found (yet)
37
    int64_t     ts_hi;       ///< frame presentation timestamp or same as pos_hi for byte seeking
38

    
39
    int64_t     last_pos;    ///< last known position of a frame, for multi-frame packets
40

    
41
    int64_t     term_ts;     ///< termination timestamp (which TS we already read)
42
    AVRational  term_ts_tb;  ///< timebase for term_ts
43
    int64_t     first_ts;    ///< first packet timestamp in this iteration (to fill term_ts later)
44
    AVRational  first_ts_tb; ///< timebase for first_ts
45

    
46
    int         terminated;  ///< termination flag for the current iteration
47
} AVSyncPoint;
48

    
49
/**
50
 * Compute a distance between timestamps.
51
 *
52
 * Distances are only comparable, if same time bases are used for computing
53
 * distances.
54
 *
55
 * @param ts_hi high timestamp
56
 * @param tb_hi high timestamp time base
57
 * @param ts_lo low timestamp
58
 * @param tb_lo low timestamp time base
59
 * @return representation of distance between high and low timestamps
60
 */
61
static int64_t ts_distance(int64_t ts_hi,
62
                           AVRational tb_hi,
63
                           int64_t ts_lo,
64
                           AVRational tb_lo)
65
{
66
    int64_t hi, lo;
67

    
68
    hi = ts_hi * tb_hi.num * tb_lo.den;
69
    lo = ts_lo * tb_lo.num * tb_hi.den;
70

    
71
    return hi - lo;
72
}
73

    
74
/**
75
 * Partial search for keyframes in multiple streams.
76
 *
77
 * This routine searches in each stream for the next lower and the next higher
78
 * timestamp compared to the given target timestamp. The search starts at the current
79
 * file position and ends at the file position, where all streams have already been
80
 * examined (or when all higher key frames are found in the first iteration).
81
 *
82
 * This routine is called iteratively with an exponential backoff to find the lower
83
 * timestamp.
84
 *
85
 * @param s                 format context
86
 * @param timestamp         target timestamp (or position, if AVSEEK_FLAG_BYTE)
87
 * @param timebase          time base for timestamps
88
 * @param flags             seeking flags
89
 * @param sync              array with information per stream
90
 * @param keyframes_to_find count of keyframes to find in total
91
 * @param found_lo          ptr to the count of already found low timestamp keyframes
92
 * @param found_hi          ptr to the count of already found high timestamp keyframes
93
 * @param first_iter        flag for first iteration
94
 */
95
static void search_hi_lo_keyframes(AVFormatContext *s,
96
                                   int64_t timestamp,
97
                                   AVRational timebase,
98
                                   int flags,
99
                                   AVSyncPoint *sync,
100
                                   int keyframes_to_find,
101
                                   int *found_lo,
102
                                   int *found_hi,
103
                                   int first_iter)
104
{
105
    AVPacket pkt;
106
    AVSyncPoint *sp;
107
    AVStream *st;
108
    int idx;
109
    int flg;
110
    int terminated_count = 0;
111
    int64_t pos;
112
    int64_t pts, dts;   // PTS/DTS from stream
113
    int64_t ts;         // PTS in stream-local time base or position for byte seeking
114
    AVRational ts_tb;   // Time base of the stream or 1:1 for byte seeking
115

    
116
    for (;;) {
117
        if (av_read_frame(s, &pkt) < 0) {
118
            // EOF or error, make sure high flags are set
119
            for (idx = 0; idx < s->nb_streams; ++idx) {
120
                if (s->streams[idx]->discard < AVDISCARD_ALL) {
121
                    sp = &sync[idx];
122
                    if (sp->pos_hi == INT64_MAX) {
123
                        // no high frame exists for this stream
124
                        (*found_hi)++;
125
                        sp->ts_hi  = INT64_MAX;
126
                        sp->pos_hi = INT64_MAX - 1;
127
                    }
128
                }
129
            }
130
            break;
131
        }
132

    
133
        idx = pkt.stream_index;
134
        st = s->streams[idx];
135
        if (st->discard >= AVDISCARD_ALL)
136
            // this stream is not active, skip packet
137
            continue;
138

    
139
        sp = &sync[idx];
140

    
141
        flg = pkt.flags;
142
        pos = pkt.pos;
143
        pts = pkt.pts;
144
        dts = pkt.dts;
145
        if (pts == AV_NOPTS_VALUE)
146
            // some formats don't provide PTS, only DTS
147
            pts = dts;
148

    
149
        av_free_packet(&pkt);
150

    
151
        // Multi-frame packets only return position for the very first frame.
152
        // Other frames are read with position == -1. Therefore, we note down
153
        // last known position of a frame and use it if a frame without
154
        // position arrives. In this way, it's possible to seek to proper
155
        // position. Additionally, for parsers not providing position at all,
156
        // an approximation will be used (starting position of this iteration).
157
        if (pos < 0)
158
            pos = sp->last_pos;
159
        else
160
            sp->last_pos = pos;
161

    
162
        // Evaluate key frames with known TS (or any frames, if AVSEEK_FLAG_ANY set).
163
        if (pts != AV_NOPTS_VALUE &&
164
            ((flg & PKT_FLAG_KEY) || (flags & AVSEEK_FLAG_ANY))) {
165
            if (flags & AVSEEK_FLAG_BYTE) {
166
                // for byte seeking, use position as timestamp
167
                ts        = pos;
168
                ts_tb.num = 1;
169
                ts_tb.den = 1;
170
            } else {
171
                // otherwise, get stream time_base
172
                ts    = pts;
173
                ts_tb = st->time_base;
174
            }
175

    
176
            if (sp->first_ts == AV_NOPTS_VALUE) {
177
                // Note down termination timestamp for the next iteration - when
178
                // we encounter a packet with the same timestamp, we will ignore
179
                // any further packets for this stream in next iteration (as they
180
                // are already evaluated).
181
                sp->first_ts    = ts;
182
                sp->first_ts_tb = ts_tb;
183
            }
184

    
185
            if (sp->term_ts != AV_NOPTS_VALUE &&
186
                av_compare_ts(ts, ts_tb, sp->term_ts, sp->term_ts_tb) > 0) {
187
                // past the end position from last iteration, ignore packet
188
                if (!sp->terminated) {
189
                    sp->terminated = 1;
190
                    ++terminated_count;
191
                    if (sp->pos_hi == INT64_MAX) {
192
                        // no high frame exists for this stream
193
                        (*found_hi)++;
194
                        sp->ts_hi  = INT64_MAX;
195
                        sp->pos_hi = INT64_MAX - 1;
196
                    }
197
                    if (terminated_count == keyframes_to_find)
198
                        break;  // all terminated, iteration done
199
                }
200
                continue;
201
            }
202

    
203
            if (av_compare_ts(ts, ts_tb, timestamp, timebase) <= 0) {
204
                // keyframe found before target timestamp
205
                if (sp->pos_lo == INT64_MAX) {
206
                    // found first keyframe lower than target timestamp
207
                    (*found_lo)++;
208
                    sp->ts_lo  = ts;
209
                    sp->pos_lo = pos;
210
                } else if (sp->ts_lo < ts) {
211
                    // found a better match (closer to target timestamp)
212
                    sp->ts_lo  = ts;
213
                    sp->pos_lo = pos;
214
                }
215
            }
216
            if (av_compare_ts(ts, ts_tb, timestamp, timebase) >= 0) {
217
                // keyframe found after target timestamp
218
                if (sp->pos_hi == INT64_MAX) {
219
                    // found first keyframe higher than target timestamp
220
                    (*found_hi)++;
221
                    sp->ts_hi  = ts;
222
                    sp->pos_hi = pos;
223
                    if (*found_hi >= keyframes_to_find && first_iter) {
224
                        // We found high frame for all. They may get updated
225
                        // to TS closer to target TS in later iterations (which
226
                        // will stop at start position of previous iteration).
227
                        break;
228
                    }
229
                } else if (sp->ts_hi > ts) {
230
                    // found a better match (actually, shouldn't happen)
231
                    sp->ts_hi  = ts;
232
                    sp->pos_hi = pos;
233
                }
234
            }
235
        }
236
    }
237

    
238
    // Clean up the parser.
239
    av_read_frame_flush(s);
240
}
241

    
242
int64_t ff_gen_syncpoint_search(AVFormatContext *s,
243
                                int stream_index,
244
                                int64_t pos,
245
                                int64_t ts_min,
246
                                int64_t ts,
247
                                int64_t ts_max,
248
                                int flags)
249
{
250
    AVSyncPoint *sync, *sp;
251
    AVStream *st;
252
    int i;
253
    int keyframes_to_find = 0;
254
    int64_t curpos;
255
    int64_t step;
256
    int found_lo = 0, found_hi = 0;
257
    int64_t min_distance, distance;
258
    int64_t min_pos = 0;
259
    int first_iter = 1;
260
    AVRational time_base;
261

    
262
    if (flags & AVSEEK_FLAG_BYTE) {
263
        // for byte seeking, we have exact 1:1 "timestamps" - positions
264
        time_base.num = 1;
265
        time_base.den = 1;
266
    } else {
267
        if (stream_index >= 0) {
268
            // we have a reference stream, which time base we use
269
            st = s->streams[stream_index];
270
            time_base = st->time_base;
271
        } else {
272
            // no reference stream, use AV_TIME_BASE as reference time base
273
            time_base.num = 1;
274
            time_base.den = AV_TIME_BASE;
275
        }
276
    }
277

    
278
    // Initialize syncpoint structures for each stream.
279
    sync = av_malloc(s->nb_streams * sizeof(AVSyncPoint));
280
    if (!sync)
281
        // cannot allocate helper structure
282
        return -1;
283

    
284
    for (i = 0; i < s->nb_streams; ++i) {
285
        st = s->streams[i];
286
        sp = &sync[i];
287

    
288
        sp->pos_lo     = INT64_MAX;
289
        sp->ts_lo      = INT64_MAX;
290
        sp->pos_hi     = INT64_MAX;
291
        sp->ts_hi      = INT64_MAX;
292
        sp->terminated = 0;
293
        sp->first_ts   = AV_NOPTS_VALUE;
294
        sp->term_ts    = ts_max;
295
        sp->term_ts_tb = time_base;
296
        sp->last_pos   = pos;
297

    
298
        st->cur_dts    = AV_NOPTS_VALUE;
299

    
300
        if (st->discard < AVDISCARD_ALL)
301
            ++keyframes_to_find;
302
    }
303

    
304
    if (!keyframes_to_find) {
305
        // no stream active, error
306
        av_free(sync);
307
        return -1;
308
    }
309

    
310
    // Find keyframes in all active streams with timestamp/position just before
311
    // and just after requested timestamp/position.
312
    step = s->pb->buffer_size;
313
    curpos = FFMAX(pos - step / 2, 0);
314
    for (;;) {
315
        url_fseek(s->pb, curpos, SEEK_SET);
316
        search_hi_lo_keyframes(s,
317
                               ts, time_base,
318
                               flags,
319
                               sync,
320
                               keyframes_to_find,
321
                               &found_lo, &found_hi,
322
                               first_iter);
323
        if (found_lo == keyframes_to_find && found_hi == keyframes_to_find)
324
            break;  // have all keyframes we wanted
325
        if (!curpos)
326
            break;  // cannot go back anymore
327

    
328
        curpos = pos - step;
329
        if (curpos < 0)
330
            curpos = 0;
331
        step *= 2;
332

    
333
        // switch termination positions
334
        for (i = 0; i < s->nb_streams; ++i) {
335
            st = s->streams[i];
336
            st->cur_dts = AV_NOPTS_VALUE;
337

    
338
            sp = &sync[i];
339
            if (sp->first_ts != AV_NOPTS_VALUE) {
340
                sp->term_ts    = sp->first_ts;
341
                sp->term_ts_tb = sp->first_ts_tb;
342
                sp->first_ts   = AV_NOPTS_VALUE;
343
            }
344
            sp->terminated = 0;
345
            sp->last_pos = curpos;
346
        }
347
        first_iter = 0;
348
    }
349

    
350
    // Find actual position to start decoding so that decoder synchronizes
351
    // closest to ts and between ts_min and ts_max.
352
    pos = INT64_MAX;
353

    
354
    for (i = 0; i < s->nb_streams; ++i) {
355
        st = s->streams[i];
356
        if (st->discard < AVDISCARD_ALL) {
357
            sp = &sync[i];
358
            min_distance = INT64_MAX;
359
            // Find timestamp closest to requested timestamp within min/max limits.
360
            if (sp->pos_lo != INT64_MAX
361
                && av_compare_ts(ts_min, time_base, sp->ts_lo, st->time_base) <= 0
362
                && av_compare_ts(sp->ts_lo, st->time_base, ts_max, time_base) <= 0) {
363
                // low timestamp is in range
364
                min_distance = ts_distance(ts, time_base, sp->ts_lo, st->time_base);
365
                min_pos = sp->pos_lo;
366
            }
367
            if (sp->pos_hi != INT64_MAX
368
                && av_compare_ts(ts_min, time_base, sp->ts_hi, st->time_base) <= 0
369
                && av_compare_ts(sp->ts_hi, st->time_base, ts_max, time_base) <= 0) {
370
                // high timestamp is in range, check distance
371
                distance = ts_distance(sp->ts_hi, st->time_base, ts, time_base);
372
                if (distance < min_distance) {
373
                    min_distance = distance;
374
                    min_pos = sp->pos_hi;
375
                }
376
            }
377
            if (min_distance == INT64_MAX) {
378
                // no timestamp is in range, cannot seek
379
                av_free(sync);
380
                return -1;
381
            }
382
            if (min_pos < pos)
383
                pos = min_pos;
384
        }
385
    }
386

    
387
    url_fseek(s->pb, pos, SEEK_SET);
388
    av_free(sync);
389
    return pos;
390
}
391

    
392
AVParserState *ff_store_parser_state(AVFormatContext *s)
393
{
394
    int i;
395
    AVStream *st;
396
    AVParserStreamState *ss;
397
    AVParserState *state = av_malloc(sizeof(AVParserState));
398
    if (!state)
399
        return NULL;
400

    
401
    state->stream_states = av_malloc(sizeof(AVParserStreamState) * s->nb_streams);
402
    if (!state->stream_states) {
403
        av_free(state);
404
        return NULL;
405
    }
406

    
407
    state->fpos = url_ftell(s->pb);
408

    
409
    // copy context structures
410
    state->cur_st                           = s->cur_st;
411
    state->packet_buffer                    = s->packet_buffer;
412
    state->raw_packet_buffer                = s->raw_packet_buffer;
413
    state->raw_packet_buffer_remaining_size = s->raw_packet_buffer_remaining_size;
414

    
415
    s->cur_st                               = NULL;
416
    s->packet_buffer                        = NULL;
417
    s->raw_packet_buffer                    = NULL;
418
    s->raw_packet_buffer_remaining_size     = RAW_PACKET_BUFFER_SIZE;
419

    
420
    // copy stream structures
421
    state->nb_streams = s->nb_streams;
422
    for (i = 0; i < s->nb_streams; i++) {
423
        st = s->streams[i];
424
        ss = &state->stream_states[i];
425

    
426
        ss->parser        = st->parser;
427
        ss->last_IP_pts   = st->last_IP_pts;
428
        ss->cur_dts       = st->cur_dts;
429
        ss->reference_dts = st->reference_dts;
430
        ss->cur_ptr       = st->cur_ptr;
431
        ss->cur_len       = st->cur_len;
432
        ss->probe_packets = st->probe_packets;
433
        ss->cur_pkt       = st->cur_pkt;
434

    
435
        st->parser        = NULL;
436
        st->last_IP_pts   = AV_NOPTS_VALUE;
437
        st->cur_dts       = AV_NOPTS_VALUE;
438
        st->reference_dts = AV_NOPTS_VALUE;
439
        st->cur_ptr       = NULL;
440
        st->cur_len       = 0;
441
        st->probe_packets = MAX_PROBE_PACKETS;
442
        av_init_packet(&st->cur_pkt);
443
    }
444

    
445
    return state;
446
}
447

    
448
void ff_restore_parser_state(AVFormatContext *s, AVParserState *state)
449
{
450
    int i;
451
    AVStream *st;
452
    AVParserStreamState *ss;
453
    av_read_frame_flush(s);
454

    
455
    if (!state)
456
        return;
457

    
458
    url_fseek(s->pb, state->fpos, SEEK_SET);
459

    
460
    // copy context structures
461
    s->cur_st                           = state->cur_st;
462
    s->packet_buffer                    = state->packet_buffer;
463
    s->raw_packet_buffer                = state->raw_packet_buffer;
464
    s->raw_packet_buffer_remaining_size = state->raw_packet_buffer_remaining_size;
465

    
466
    // copy stream structures
467
    for (i = 0; i < state->nb_streams; i++) {
468
        st = s->streams[i];
469
        ss = &state->stream_states[i];
470

    
471
        st->parser        = ss->parser;
472
        st->last_IP_pts   = ss->last_IP_pts;
473
        st->cur_dts       = ss->cur_dts;
474
        st->reference_dts = ss->reference_dts;
475
        st->cur_ptr       = ss->cur_ptr;
476
        st->cur_len       = ss->cur_len;
477
        st->probe_packets = ss->probe_packets;
478
        st->cur_pkt       = ss->cur_pkt;
479
    }
480

    
481
    av_free(state->stream_states);
482
    av_free(state);
483
}
484

    
485
static void free_packet_list(AVPacketList *pktl)
486
{
487
    AVPacketList *cur;
488
    while (pktl) {
489
        cur = pktl;
490
        pktl = cur->next;
491
        av_free_packet(&cur->pkt);
492
        av_free(cur);
493
    }
494
}
495

    
496
void ff_free_parser_state(AVFormatContext *s, AVParserState *state)
497
{
498
    int i;
499
    AVParserStreamState *ss;
500

    
501
    if (!state)
502
        return;
503

    
504
    for (i = 0; i < state->nb_streams; i++) {
505
        ss = &state->stream_states[i];
506
        if (ss->parser)
507
            av_parser_close(ss->parser);
508
        av_free_packet(&ss->cur_pkt);
509
    }
510

    
511
    free_packet_list(state->packet_buffer);
512
    free_packet_list(state->raw_packet_buffer);
513

    
514
    av_free(state->stream_states);
515
    av_free(state);
516
}
517