[FFmpeg-devel] [PATCH 1/3] Add av_build_index

[Michael Chinen]

On Thu, Aug 19, 2010 at 10:33 AM, Michael Chinen <mchinen at gmail.com> wrote:
> On Tue, Aug 17, 2010 at 1:55 PM, Michael Niedermayer <michaelni at gmx.at> wrote:
>> On Sun, Aug 15, 2010 at 08:43:16AM +0200, Michael Chinen wrote:
>>> Hi,
>>>
>>> On Sun, Aug 15, 2010 at 2:32 AM, Michael Chinen <mchinen at gmail.com> wrote:
>>> [...]
>>> >> With these 3 plus FLAC parser patches, some formats should provide
>>> >> sample-accurate seeking, right? Which are those? What would have to be
>>> >> done to, say, the (ASF demuxer +) WMA decoder (or any other audio
>>> >> format) to make it sample-accurate?
>>> >
>>> > ogg, FLAC, mp3 are the audio formats provide sample accurate seeking.
>>> > asf doesn't work well yet, and I'm looking into it.
>>>
>>> Okay, this updated patch plus this 0004 patch for asfdec.c which
>>> depends on 0001 (but is independent of 0002 and 0003) will give
>>> support for asfdec.c and allow formats without parsers to work by
>>> introducing a new virtual function into AVInputFormat for flushing.
>>>
>>> There are also some bugfixes detailed in the patch log.
>>>
>>> I wasn't sure how to send 0004 since it would change the email subject
>>> and break the thread.
>>> Please let me know if there is a more preferred way.
>>>
>>> Michael
>>
>>> ?avformat.h | ? 34 +++++
>>> ?utils.c ? ?| ?407 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
>>> ?2 files changed, 424 insertions(+), 17 deletions(-)
>>> 85e730e8c6800c0bf1996310942d5b8405242666 ?0001-Add-av_build_index.patch
>>> From 91192c8e856a7baa64cae45d725d3e5d8f8b02d2 Mon Sep 17 00:00:00 2001
>>> From: Michael Chinen <mchinen at gmail.com>
>>> Date: Fri, 13 Aug 2010 05:43:02 +0200
>>> Subject: [PATCH 1/4] Add av_build_index
>>> ?Also adds static av_seek_frame_table function and integration into existing seek api
>>>
>>> Second patch submission touchups:
>>> make sure first timestamp is set
>>> build index correctly for formats that don't have parsers or AVFMT_GENERIC_INDEX
>>> flush and update timestamp for non-parallel building.
>>> Add read_flush to AVInputFormat
>>> Provides av_build_index support for AVInputFormats without parsers that hold state
>>> ---
>>> ?libavformat/avformat.h | ? 34 ++++
>>> ?libavformat/utils.c ? ?| ?407 ++++++++++++++++++++++++++++++++++++++++++++++--
>>> ?2 files changed, 424 insertions(+), 17 deletions(-)
>>>
>>> diff --git a/libavformat/avformat.h b/libavformat/avformat.h
>>> index 452aea6..13184c9 100644
>>> --- a/libavformat/avformat.h
>>> +++ b/libavformat/avformat.h
>>> @@ -408,6 +408,11 @@ typedef struct AVInputFormat {
>>>
>>> ? ? ?const AVMetadataConv *metadata_conv;
>>>
>>> + ? ?/**
>>> + ? ? * Reset the format's state to one that does not rely on previous input.
>>> + ? ? */
>>> + ? ?int (*read_flush)(struct AVFormatContext *s);
>>
>> iam not sure about this one, can we postpone this hunk please to later
>
> Ok, moved to 0006.2 patch
>
>>
>>
>>> +
>>> ? ? ?/* private fields */
>>> ? ? ?struct AVInputFormat *next;
>>> ?} AVInputFormat;
>>> @@ -586,6 +591,19 @@ typedef struct AVStream {
>>> ? ? ? * Number of frames that have been demuxed during av_find_stream_info()
>>> ? ? ? */
>>> ? ? ?int codec_info_nb_frames;
>>> +
>>> + ? ?/* new av_seek_frame_table() support */
>>> +#define AV_SEEKTABLE_BUILDING ? 0x0001 /**< if set the index is being built ? */
>>
>>> +#define AV_SEEKTABLE_CBR ? ? ? ?0x0002 /**< if set the file is constant bit
>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?rate and the index is implicit ? ?*/
>>
>> the doxy is a bit terse
>
> Improved it.
>
>>
>>
>> [...]
>>> @@ -1337,8 +1338,28 @@ void ff_reduce_index(AVFormatContext *s, int stream_index)
>>>
>>> ? ? ?if((unsigned)st->nb_index_entries >= max_entries){
>>> ? ? ? ? ?int i;
>>> - ? ? ? ?for(i=0; 2*i<st->nb_index_entries; i++)
>>> - ? ? ? ? ? ?st->index_entries[i]= st->index_entries[2*i];
>>> + ? ? ? ?if(st->seek_table_flags & AV_SEEKTABLE_BUILDING) {
>>> + ? ? ? ? ? ?int j ? ? ? ? ? ?= 0;
>>> + ? ? ? ? ? ?int nb_reduced ? = max_entries / 2;
>>> + ? ? ? ? ? ?int64_t ts_inc ? = (st->index_entries[st->nb_index_entries - 1].timestamp
>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?- st->index_entries[0].timestamp) / nb_reduced;
>>> + ? ? ? ? ? ?int64_t start_ts = st->index_entries[0].timestamp;
>>> + ? ? ? ? ? ?/* reinsert for even distribution of timestamps */
>>> + ? ? ? ? ? ?for (i = 0; i < nb_reduced; i++) {
>>> + ? ? ? ? ? ? ? ?if (j >= st->nb_index_entries)
>>> + ? ? ? ? ? ? ? ? ? ?break;
>>> + ? ? ? ? ? ? ? ?st->index_entries[i] = st->index_entries[j++];
>>> + ? ? ? ? ? ? ? ?while (j < st->nb_index_entries &&
>>> + ? ? ? ? ? ? ? ? ? ? ? (st->index_entries[j].timestamp <
>>> + ? ? ? ? ? ? ? ? ? ? ? ?start_ts + (i + 1) * ts_inc)) {
>>> + ? ? ? ? ? ? ? ? ? ?j++;
>>> + ? ? ? ? ? ? ? ?}
>>> + ? ? ? ? ? ?}
>>> + ? ? ? ? ? ?av_log(s,AV_LOG_DEBUG,"reduced index to size %d (max = %d)\n", i, max_entries);
>>> + ? ? ? ?} else {
>>> + ? ? ? ? ? ?for (i = 0; 2 * i < st->nb_index_entries; i++)
>>> + ? ? ? ? ? ? ? ?st->index_entries[i] = st->index_entries[2*i];
>>> + ? ? ? ?}
>>
>> this is reimplementing existing code in a different way.
>> you can use the existing code or improve the existing code and use it
>> but you cant duplicate it.
>
> I removed the original method and replaced it with mine. ?I don't
> think there are cases where we need an uneven index. ?I tested this on
> 5 hour mp3s/ogg and it handles okay (seek resolution is about 0.5s)
>
>>
>>
>>> ? ? ? ? ?st->nb_index_entries= i;
>>> ? ? ?}
>>> ?}
>>> @@ -1349,6 +1370,10 @@ int av_add_index_entry(AVStream *st,
>>> ? ? ?AVIndexEntry *entries, *ie;
>>> ? ? ?int index;
>>>
>>> + ? ?/* Don't add index if we already have a complete one */
>>> + ? ?if (st->seek_table_flags & AV_SEEKTABLE_FINISHED)
>>> + ? ? ? ?return av_index_search_timestamp(st, timestamp, AVSEEK_FLAG_ANY);
>>> +
>>> ? ? ?if((unsigned)st->nb_index_entries + 1 >= UINT_MAX / sizeof(AVIndexEntry))
>>> ? ? ? ? ?return -1;
>>>
>>
>> why is this hunk needed?
>
> I thought we were supposed to return valid index (as the function does
> at end,) but I grepped and no one seems to use the return value. ?I am
> or'ing the check with the next if instead.
>
>>
>>
>>> @@ -1361,21 +1386,31 @@ int av_add_index_entry(AVStream *st,
>>>
>>> ? ? ?st->index_entries= entries;
>>>
>>> - ? ?index= av_index_search_timestamp(st, timestamp, AVSEEK_FLAG_ANY);
>>> + ? ?/* If we are building the table, the indicies added in order, so we don't
>>> + ? ? ? have to do expensive searching. ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?*/
>>> + ? ?if (st->seek_table_flags & AV_SEEKTABLE_BUILDING) {
>>> + ? ? ? ?index = st->nb_index_entries++;
>>> + ? ? ? ?ie = &st->index_entries[index];
>>> + ? ?} else {
>>> + ? ? ? ?index = av_index_search_timestamp(st, timestamp, AVSEEK_FLAG_ANY);
>>
>> improve av_index_search_timestamp() if there is a problem
>
> ?Modifying av_index_search_timestamp would require introduction of a
> new flag (since at least the avi decoder uses
> av_index_search_timestamp in their read_packet). ?So I went with an
> alternate solution does not modify av_index_search_timestamp but
> eliminates code duplication. ?It simply sets index to -1 if the table
> is building.
>
>
>>
>>
>>>
>>> - ? ?if(index<0){
>>> - ? ? ? ?index= st->nb_index_entries++;
>>> - ? ? ? ?ie= &entries[index];
>>> - ? ? ? ?assert(index==0 || ie[-1].timestamp < timestamp);
>>> - ? ?}else{
>>> - ? ? ? ?ie= &entries[index];
>>> - ? ? ? ?if(ie->timestamp != timestamp){
>>> - ? ? ? ? ? ?if(ie->timestamp <= timestamp)
>>> - ? ? ? ? ? ? ? ?return -1;
>>> - ? ? ? ? ? ?memmove(entries + index + 1, entries + index, sizeof(AVIndexEntry)*(st->nb_index_entries - index));
>>> - ? ? ? ? ? ?st->nb_index_entries++;
>>> - ? ? ? ?}else if(ie->pos == pos && distance < ie->min_distance) //do not reduce the distance
>>> - ? ? ? ? ? ?distance= ie->min_distance;
>>> + ? ? ? ?if (index < 0){
>>> + ? ? ? ? ? ?index = st->nb_index_entries++;
>>> + ? ? ? ? ? ?ie = &entries[index];
>>> + ? ? ? ? ? ?assert(index == 0 || ie[-1].timestamp < timestamp);
>>> + ? ? ? ?} else {
>>> + ? ? ? ? ? ?ie= &entries[index];
>>> + ? ? ? ? ? ?if (ie->timestamp != timestamp){
>>> + ? ? ? ? ? ? ? ?if (ie->timestamp <= timestamp)
>>
>> reindention
>
> These changes are gone due to the above hunk change.
>
>>
>>
>> [...]
>>
>>> + ? ? ? ?av_log(s, AV_LOG_DEBUG,
>>> + ? ? ? ? ? ? ? "SEEK TABLE: copying over parallel frames\n");
>>> + ? ? ? ?for(i = 0; i < s->nb_streams; i++) {
>>> + ? ? ? ? ? ?st = s->streams[i];
>>> + ? ? ? ? ? ?av_free(st->index_entries);
>>> + ? ? ? ? ? ?st->index_entries ? ? ? ? ? ? ? ?= st->parallel_index_entries;
>>> + ? ? ? ? ? ?st->nb_index_entries ? ? ? ? ? ? = st->parallel_nb_index_entries;
>>> + ? ? ? ? ? ?st->index_entries_allocated_size = st->parallel_index_entries_allocated_size;
>>> + ? ? ? ? ? ?st->parallel_index_entries ? ? ? = NULL;
>>> + ? ? ? ? ? ?st->seek_table_flags |= AV_SEEKTABLE_FINISHED;
>>> + ? ? ? ?}
>>> + ? ?}
>>> +
>>
>>> + ? ?st = s->streams[stream_index];
>>> + ? ?if (st->seek_table_flags & AV_SEEKTABLE_FINISHED)
>>> + ? ? ? ?return av_seek_frame_table(s, stream_index, timestamp, flags);
>>
>> why do we need this?
>> once the index is complete the existing seek functions should use the index
>
> The table_seek also does CBR, but I moved this to av_seek_frame_cbr
> and merged the leftover into av_seek_frame_generic.
>
>>
>>
>>> +
>>> ? ? ?/* first, we try the format specific seek */
>>> ? ? ?if (s->iformat->read_seek)
>>> ? ? ? ? ?ret = s->iformat->read_seek(s, stream_index, timestamp, flags);
>>> @@ -3686,3 +3813,249 @@ int ff_write_chained(AVFormatContext *dst, int dst_stream, AVPacket *pkt,
>>> ? ? ?return av_write_frame(dst, &local_pkt);
>>> ?}
>>>
>>> +#define FF_DETECT_CBR_FPS_GUESS 10 /**< fps to assume if unknown */
>>
>> this doesnt look very nice
>
> Expanded the comment; maybe this helps.
>
>>
>>
>>> +static int av_detect_cbr(AVFormatContext *s, AVStream *st) {
>>> + ? ?//check the stream's codec to see if a number of frames are listed,
>>> + ? ?//but we can't assume that it is available.
>>> + ? ?if (s->data_offset > 0 && s->file_size > 0 &&
>>> + ? ? ? ?s->data_offset != s->file_size && st->codec && st->duration > 0) {
>>> + ? ? ? ?double sec_duration = st->duration * av_q2d(st->time_base);
>>
>> floats should be avoided to have exact and reproduceable across platform
>> behavior.
>
> done.
>
>>
>>
>> [...]
>>
>>> + ? ? ? ?/* Delete old index entries to get a clean table. */
>>> + ? ? ? ?for(i = 0; i < build_ic->nb_streams; i++) {
>>> + ? ? ? ? ? ?int64_t start_ts;
>>> + ? ? ? ? ? ?build_ic->streams[i]->seek_table_flags |= AV_SEEKTABLE_BUILDING;
>>> + ? ? ? ? ? ?build_ic->streams[i]->nb_index_entries = 0;
>>> + ? ? ? ? ? ?AVStream* seek_st;
>>
>> mixes declarations and statements
>> also please try tools/patcheck
>
> Fixed.
>
>>
>>
>>> + ? ? ? ? ? ?seek_st = build_ic->streams[i];
>>> + ? ? ? ? ? ?start_ts = seek_st->start_time != AV_NOPTS_VALUE ?
>>> + ? ? ? ? ? ? ? ? ? ? ? seek_st->start_time :
>>> + ? ? ? ? ? ? ? ? ? ? ?(seek_st->first_dts ?!= AV_NOPTS_VALUE ?
>>> + ? ? ? ? ? ? ? ? ? ? ? seek_st->first_dts ?: 0);
>>> +
>>> + ? ? ? ? ? ?av_update_cur_dts(build_ic, build_ic->streams[i],
>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?start_ts);
>>> + ? ? ? ?}
>>> +
>>> + ? ? ? ?orig_flags = build_ic->flags;
>>> + ? ? ? ?build_ic->flags |= AVFMT_FLAG_GENPTS;
>>> + ? ? ? ?for (;;) {
>>> + ? ? ? ? ? ?do {
>>> + ? ? ? ? ? ? ? ?ret = av_read_frame(build_ic, &pkt);
>>> + ? ? ? ? ? ?} while (ret == AVERROR(EAGAIN));
>>> + ? ? ? ? ? ?if (ret < 0)
>>> + ? ? ? ? ? ? ? ?break;
>>> + ? ? ? ? ? ?av_free_packet(&pkt);
>>> + ? ? ? ?}
>>
>> duplicates code from av_seek_frame_generic()
>
> The contents of the for loop are different and it involves a break, so
> I don't see how to refactor this besides moving the three lines of
> code that make the do-while loop up. ?Is this what you mean?
>
>>
>>
>>> + ? ? ? ?build_ic->flags = orig_flags;
>>> + ? ? ? ?for(i = 0; i < build_ic->nb_streams; i++)
>>> + ? ? ? ? ? ?build_ic->streams[i]->seek_table_flags ^= AV_SEEKTABLE_BUILDING;
>>
>> i think |= and &=~ are more clear in terms of readability
>
> Done.
>
>>
>>
>>> +
>>> + ? ? ? ?ret = 0;
>>> + ? ?cleanup:
>>> + ? ? ? ?/* If built on a parallel context, mark the original context. */
>>> + ? ? ? ?if (flags & AV_BUILD_INDEX_PARALLEL) {
>>> + ? ? ? ? ? ?if (build_ic) {
>>> + ? ? ? ? ? ? ? ?for (i = 0; i < build_ic->nb_streams; i++) {
>>> + ? ? ? ? ? ? ? ? ? ?if (ret >= 0) {
>>> + ? ? ? ? ? ? ? ? ? ? ? ?av_log(s, AV_LOG_DEBUG,
>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? "SEEK TABLE: marking %i frames from"
>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? " parallel stream ready for copy\n",
>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? build_ic->streams[i]->nb_index_entries);
>>> + ? ? ? ? ? ? ? ? ? ? ? ?s->streams[i]->parallel_index_entries =
>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ?build_ic->streams[i]->index_entries;
>>> + ? ? ? ? ? ? ? ? ? ? ? ?s->streams[i]->parallel_nb_index_entries =
>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ?build_ic->streams[i]->nb_index_entries;
>>> + ? ? ? ? ? ? ? ? ? ? ? ?s->streams[i]->parallel_index_entries_allocated_size =
>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ?build_ic->streams[i]->index_entries_allocated_size;
>>
>> i think this should ignore the 80 char limit as it would be more readable then
>
> Done.
>
>>
>>
>>> + ? ? ? ? ? ? ? ? ? ? ? ?build_ic->streams[i]->index_entries = NULL;
>>> + ? ? ? ? ? ? ? ? ? ?}
>>> + ? ? ? ? ? ? ? ? ? ?avcodec_close(build_ic->streams[i]->codec);
>>> + ? ? ? ? ? ? ? ?}
>>
>>> + ? ? ? ? ? ? ? ?s->flags |= AVFMT_FLAG_TABLE_READY;
>>
>> this is possibly not thread safe or at least asking for future bugs
>> a variable should not be written to by more than 1 thread without
>> locking. |= is not guranteed to be an atomic operation,
>> bits are not independent variables
>
> Yes, sorry about this. ?Now using independent variable (added to
> AVFormatContext) set from building thread and do not unset it in main
> thread. ?Main thread now sets AVFormatContext flag
> AVFMT_FLAG_INDEX_BUILT instead of unsetting.
>
>>
>>
>>> + ? ? ? ? ? ? ? ?av_close_input_file(build_ic);
>>> + ? ? ? ? ? ?}
>>> + ? ? ? ?}
>>> + ? ? ? ?if (ret < 0)
>>> + ? ? ? ? ? ?return ret;
>>> + ? ?}
>>> +
>>
>>> + ? ?/* Since we probably have moved the read cursor to the end,
>>> + ? ? ? return seek to start of stream for non-parallel clients.
>>> + ? ? ? Not sure if this the desired behavior, but it seems convinient. */
>>> + ? ?if (!(flags & AV_BUILD_INDEX_PARALLEL) &&
>>> + ? ? ? ?!(st->seek_table_flags & AV_SEEKTABLE_COPIED)) {
>>> + ? ? ? ?int64_t start_ts;
>>> +
>>> + ? ? ? ?ff_read_frame_flush(s);
>>> + ? ? ? ?for(i = 0; i < s->nb_streams; i++)
>>> + ? ? ? ? ? ?if (s->streams[i]->nb_index_entries)
>>> + ? ? ? ? ? ? ? ?s->streams[i]->seek_table_flags |= AV_SEEKTABLE_FINISHED;
>>> +
>>> + ? ? ? ?start_ts = st->start_time != AV_NOPTS_VALUE ? st->start_time :
>>> + ? ? ? ? ? ? ? ? ?(st->first_dts ?!= AV_NOPTS_VALUE ? st->first_dts ?: 0);
>>> + ? ? ? ?if ((ret = av_seek_frame(s, stream_index,
>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? start_ts, AVSEEK_FLAG_ANY)) < 0) {
>>> + ? ? ? ? ? ?int data_offset = (s->data_offset < 0) ||
>>> + ? ? ? ? ? ? ? ?(s->data_offset >= s->file_size) ? 0 : s->data_offset;
>>> +
>>> + ? ? ? ? ? ?av_log(s, AV_LOG_DEBUG,
>>> + ? ? ? ? ? ? ? ? ? "SEEK TABLE: error seeking using new index: %i,"
>>> + ? ? ? ? ? ? ? ? ? " trying url_fseek\n",
>>> + ? ? ? ? ? ? ? ? ? ret);
>>> +
>>> + ? ? ? ? ? ?/* last ditch effort to seek using the file pointer. */
>>> + ? ? ? ? ? ?if ((ret = url_fseek(s->pb, data_offset, SEEK_SET)) < 0) {
>>> + ? ? ? ? ? ? ? ?av_log(s,AV_LOG_DEBUG,
>>> + ? ? ? ? ? ? ? ? ? ? ? "SEEK TABLE: error seeking with url_fseek: %i\n",
>>> + ? ? ? ? ? ? ? ? ? ? ? ret);
>>> + ? ? ? ? ? ? ? ?return ret;
>>> + ? ? ? ? ? ?}
>>> + ? ? ? ?}
>>> + ? ?}
>>
>> is all this needed?
>> or does a subset of this work as well?
>
> This was debug junk from when it didn't work as well. ?Reduced to a subset.
>
> Thanks for the review.
>
> Michael
>
> [...]
>

Updated patch fixes the modified ff_reduce_index to handle valid
packets that have timestamp AV_NOPTS_VALUE.

Also attaching asf and read_flush addition patches because (indexes
have changed)

Michael
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Add-av_build_index.patch
Type: application/octet-stream
Size: 21160 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20100825/e659e6a8/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0004-Add-read_flush-to-AVInputFormat.patch
Type: application/octet-stream
Size: 1434 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20100825/e659e6a8/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0005-Add-av_build_index-support-to-asf.patch
Type: application/octet-stream
Size: 663 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20100825/e659e6a8/attachment-0002.obj>