[FFmpeg-devel] [PATCH 03/23] avformat/matroskaenc: Use random TrackUID

[Michael Niedermayer]

On Wed, Nov 27, 2019 at 05:57:56PM +0100, Andreas Rheinhardt wrote:
> On Wed, Nov 27, 2019 at 4:50 PM Michael Niedermayer <michael at niedermayer.cc>
> wrote:
> 
> > On Wed, Nov 27, 2019 at 08:25:13AM +0100, Andreas Rheinhardt wrote:
> > > On Mon, Nov 25, 2019 at 2:57 PM Michael Niedermayer
> > <michael at niedermayer.cc>
> > > wrote:
[...]
> 
> >
> > [...]
> > > >
> > > > [...]
> > > > >
> > > > >
> > > > > > and, this
> > > > > > +    /* Test the numbers from 1 to i. */
> > > > > > +    for (int j = 1, k; j < i + 1; j++) {
> > > > > > +        for (k = 0; k < i; k++) {
> > > > > > +            if (tracks[k].uid == j)
> > > > > > +                break;
> > > > > > +        }
> > > > > > +        if (k == i)
> > > > > > +            return j;
> > > > > > +    }
> > > > > >
> > > > > > just smells "wrong"
> > > > > >
> > > > > > This code would only be executed if using AVLFG would repeatedly
> > lead
> > > > to
> > > > > collisions;
> > > >
> > > > yes but this doesnt smell right
> > > > if your random number generator produces no random numbers i dont think
> > > > adding +1 is the solution.
> > > > I mean if that really happens, theres some bug either in LFG the seed
> > > > generation
> > > > or in how it is used.
> > > >
> > > > Yes, this code was only intended to be run if the random number
> > generator
> > > is completely buggy. But it seems that this can unfortunately not ruled
> > out
> > > completely (
> >
> > >
> > https://www.phoronix.com/scan.php?page=news_item&px=AMD-RdRand-Disable-15h-16h
> > > ).
> >
> > The fix to this does not belong into a caller of av_get_random_seed()
> > if thats fixed / worked around in CPU, Bios, OS, or in av_get_random_seed()
> > i dont know but definitly not the user of av_get_random_seed().
> > If av_get_random_seed() is bad thats bad and needs to be fixed
> >
> > Also lets assume av_get_random_seed() is bad and returns -1 always
> > or another constant.
> > The code still must not fail like this. the seeded PRNG must still
> > function properly and produce a few differentg values.
> > If its statistics are 100% duplicates thats a failure of the PRNG.
> >
> >  First, are you saying that a caller can rely on the values being
> different so that I can simply remove the last-resort code and assert that
> everything is fine? (Or should I let the initial loop using AVLFG run until
> it has found a good value in the hope that it will terminate eventually?)

I expect the LFG to produce billions of distinct values for every seed.
If you find a seed for which it does not do this i would consider this a
bug and iam insterrested in such a case.
Distinct values may of course be non consecutive as one would expect
from random numbers


> 
> Second, given that only one call to av_get_random_seed() is ever performed,
> the question of whether it always returns -1 is irrelevant here: If some
> seed exists that leads to these collisions, then it is possible for these
> collisions to happen even when the random seed is truly random (in such a
> case, it would be unlikely, of course). Is there such a seed? I don't know.
> I only know that if the state of the AVLFG is completely zero, then
> av_lfg_get() will always return zero. This is the only state with the
> property that the state is not altered by any av_lfg_get(), but this does
> not preclude the output to be e.g. periodic.

its not needed to be all zero. a pathological case already occurs if
all state values are even. I suspect that does not happen for any seed though.
its statistically unlikely.

Thanks

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

"Nothing to hide" only works if the folks in power share the values of
you and everyone you know entirely and always will -- Tom Scott

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 181 bytes
Desc: not available
URL: <https://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20191127/01b96fbe/attachment.sig>