[FFmpeg-devel] [PATCH 5/6] avfilter/formats: Simplify cleanup for ff_merge_* functions

[Nicolas George]

Andreas Rheinhardt (12020-08-08):
> I was thinking about this part of the MERGE_FORMATS macro:
> 
>         for (i = 0; i < a->nb; i++)
>             for (j = 0; j < b->nb; j++)
>                 if (a->fmts[i] == b->fmts[j]) {
>                     if(k >= FFMIN(a->nb, b->nb)){
>                         av_log(NULL, AV_LOG_ERROR, "Duplicate formats in
> %s detected\n", __FUNCTION__);
>                         av_free(ret->fmts);
>                         av_free(ret);
>                         return NULL;
>                     }
>                     ret->fmts[k++] = a->fmts[i];
>                 }
> 
> Said check is not sufficient to ensure that there are no duplicates in
> ret->fmts, of course. It has been added in the merge commit 1cbf7fb4345
> as an additional safety check to ensure that one does not write beyond
> the end of ret->fmts (it has FFMIN(a->nb, b->nb) entries). Yet this goal
> could also be achieved in a simpler way: If a->nb <= b->nb, one could
> simply rewrite the above to

This is only a protection against internal bugs, since lists should not
contain duplicates in the first place. As such it should have been an
assert. If we no longer need it, it would probably be better to make a
conditional complete test for duplicates somewhere.

>         for (i = 0; i < a->nb; i++)
>             for (j = 0; j < b->nb; j++)
>                 if (a->fmts[i] == b->fmts[j]) {
>                     ret->fmts[k++] = a->fmts[i];
>                     break;
>                 }
> 
> This ensures that every entry of a will end up at most once in ret. And
> if one were simply allowed to switch a and b, one could ensure a->nb <=
> b->nb easily. ff_merge_channel_layouts() already does something similar.

I noticed something similar when refreshing my memory about this.
Indeed, breaking out of the loop when a match is found would make the
same guarantee, and a nice optimization for a quadratic algorithm.

Now, I can confirm, the order of formats in the array is not relevant
for the rest of the negotiation.

> As a next step one could then even reuse the a->fmts array for ret->fmts
> (or simply reuse a altogether); this is possible because k <= i at the
> beginning of every iteration of the outer loop.

Indeed.

> Notice that if there is a total ordering of all the formats and if both

These are mostly numbers, we can choose to use the numeric ordering or a
variant.

> a->fmts and b->fmts are ordered according to this ordering, then
> ret->fmts will also ordered in that way (regardless of whether one swaps
> or not).

Even better: if the lists are ordered, then we can switch from a
quadratic algorithm to a linear one. Good idea.

Regards,

-- 
  Nicolas George
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: not available
URL: <https://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20200812/5b379d9f/attachment.sig>