[FFmpeg-devel] [PATCH 1/5] mxfdec: Parse IndexTableSegments and convert them into AVIndexEntry arrays

[Tomas Härdin]

On Mon, 2011-11-14 at 16:03 +0100, Michael Niedermayer wrote:
> qsort() is O(n log(n)) for reverse order
> qsort() breaks down to O(n^2) when elements are ordered

Ah, I had it that it was the other way around. Anyway, not many entries.
We can bother if someone finds a sample with tens of thousands of
segments.

> [...]
> > > > +        st->index_entries_allocated_size += duration * sizeof(*st->index_entries);
> > > > +        if (st->index_entries_allocated_size / sizeof(*st->index_entries) < st->nb_index_entries + duration) {
> > > > +            av_log(mxf->fc, AV_LOG_ERROR, "index_entries_allocated_size overflow; "
> > > > +                                          "segment duration %i unreasonably large?\n", duration);
> > > > +            return AVERROR_INVALIDDATA;
> > > > +        }
> > > > +        if (!(st->index_entries = av_realloc(st->index_entries, st->index_entries_allocated_size))) {
> > > > +            av_free(sorted_segments);
> > > > +            return AVERROR(ENOMEM);
> > > > +        }
> > > > +        for (k = 0; k < duration; k++) {
> > > > +            AVIndexEntry *e = &st->index_entries[st->nb_index_entries];
> > > > +            if (k < tableseg->nb_index_entries) {
> > > > +                e->pos = tableseg->stream_offset_entries[k];
> > > > +                if (n_delta < tableseg->nb_delta_entries) {
> > > > +                    if (n_delta < tableseg->nb_delta_entries - 1) {
> > > > +                        e->size =
> > > > +                            tableseg->slice_offset_entries[k][tableseg->slice[n_delta+1]-1] +
> > > > +                            tableseg->element_delta[n_delta+1] -
> > > > +                            tableseg->element_delta[n_delta];
> > > > +                        if (tableseg->slice[n_delta] > 0)
> > > > +                            e->size -= tableseg->slice_offset_entries[k][tableseg->slice[n_delta]-1];
> > > > +                    } else if (k < duration - 1) {
> > > > +                        e->size = tableseg->stream_offset_entries[k+1] -
> > > > +                            tableseg->stream_offset_entries[k] -
> > > > +                            tableseg->slice_offset_entries[k][tableseg->slice[tableseg->nb_delta_entries-1]-1] -
> > > > +                            tableseg->element_delta[tableseg->nb_delta_entries-1];
> > > > +                    } else
> > > > +                        e->size = 0;
> > > > +                    if (tableseg->slice[n_delta] > 0)
> > > > +                        e->pos += tableseg->slice_offset_entries[k][tableseg->slice[n_delta]-1];
> > > > +                    e->pos += tableseg->element_delta[n_delta];
> > > > +                }
> > > > +                e->flags = !(tableseg->flag_entries[k] & 0x30) ? AVINDEX_KEYFRAME : 0;
> > > > +            } else {
> > > > +                e->pos = (int64_t)k * tableseg->edit_unit_byte_count + accumulated_offset;
> > > > +                if (n_delta < tableseg->nb_delta_entries - 1)
> > > > +                    e->size = tableseg->element_delta[n_delta+1] - tableseg->element_delta[n_delta];
> > > > +                else {
> > > > +                    /* use smaller size for last sample if we should */
> > > > +                    if (last_sample_size && k == duration - 1)
> > > > +                        e->size = last_sample_size;
> > > > +                    else
> > > > +                        e->size = tableseg->edit_unit_byte_count;
> > > > +                    if (tableseg->nb_delta_entries)
> > > > +                        e->size -= tableseg->element_delta[tableseg->nb_delta_entries-1];
> > > > +                }
> > > > +                if (n_delta < tableseg->nb_delta_entries)
> > > > +                    e->pos += tableseg->element_delta[n_delta];
> > > > +                e->flags = AVINDEX_KEYFRAME;
> > > > +            }
> > > > +            if (k > 0 && e->pos < mxf->first_essence_length && accumulated_offset == 0)
> > > > +                e->pos += mxf->first_essence_kl_length;
> > > > +            e->timestamp = sample_duration * st->nb_index_entries++;
> > > > +            av_dlog(mxf->fc, "Stream %d IndexEntry %d n_Delta %d Offset %"PRIx64" Timestamp %"PRId64"\n",
> > > > +                    st->index, st->nb_index_entries, n_delta, e->pos, e->timestamp);
> > > > +            e->pos += mxf->essence_offset;
> > > > +            e->min_distance = 0;
> > > > +        }
> > > > +        accumulated_offset += segment_size;
> > > > +    }
> > > 
> > > why does this not use av_add_index_entry() ?
> > 
> > To avoid needless allocations. IIRC Baptiste suggested that I keep this
> > approach. I see that av_add_index_entry() makes use of
> > index_entries_allocated_size, meaning simply keeping the realloc part
> > should be enough. It could perhaps be broken out into a function like
> > ff_alloc_extra_index_entries() in a separate patch though.
> 
> av_realloc() is slow, av_fast_realloc() is faster (by reallocating in
> larger steps and not reducing size)
> av_add_index_entry() uses the fast variant.
> 
> the problem av_add_index_entry() has currently is when adding
> millions of entries in non sequential order.
> 
> also duration * sizeof(*st->index_entries) needs to be checked for
> integer overflow unless something implicitly prevents it from becoming
> too large as otherwise the array may be quite a bit smaller than the
> data written into it.
> av_add_index_entry() already does that check

Fair enough. I switched to using av_add_index_entry(), simplifying the
code quite a bit.
Reworking the patch revealed that one possible branch left size unset
(above "flags = !(tableseg->flag_entries[k] & 0x30) ? AVINDEX_KEYFRAME :
0;"). I'm setting size to zero there for now, just like a few lines
further up. Not sure if it makes sense though.

Updated patch attached.

/Tomas
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-mxfdec-Parse-IndexTableSegments-and-convert-them-int.patch
Type: text/x-patch
Size: 14987 bytes
Desc: not available
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20111118/217ccab8/attachment.bin>