[FFmpeg-devel] [PATCH v2 2/2] random_seed: Improve behaviour with small timer increments with high precision timers

[Michael Niedermayer]

On Mon, Feb 10, 2025 at 03:54:51PM +0200, Martin Storsjö wrote:
> On Sun, 9 Feb 2025, Michael Niedermayer wrote:
> 
> > Hi Martin
> > 
> > On Fri, Feb 07, 2025 at 12:04:53AM +0200, Martin Storsjö wrote:
> > > On Thu, 6 Feb 2025, Michael Niedermayer wrote:
> > > 
> > > > On Thu, Feb 06, 2025 at 02:38:48PM +0200, Martin Storsjö wrote:
> > > > > On Thu, 6 Feb 2025, Michael Niedermayer wrote:
> > > > > 
> > > > > > > +            // If the timer resolution is high, and we get the same timer
> > > > > > > +            // value multiple times, use variances in the number of repeats
> > > > > > > +            // of each timer value as entropy. If the number of repeats changed,
> > > > > > > +            // proceed to the next index.
> > > > > > 
> > > > > > Does it still work if you check against the last 2 ?
> > > > > > or does this become too slow ?
> > > > > > What iam thinking of is this
> > > > > > 
> > > > > > 7,8,7,8,8,7,8,7,8,8,7,8,7,8,8,7,8,7,8,8,... and a 9 or 6 or further distant would trigger it
> > > > > > 
> > > > > > I assume both the CPU clock and the wall time are quite precisse so if we
> > > > > > just compare them the entropy could be low even with 2 alternating values
> > > > > 
> > > > > Yes, that still works for making it terminate in a reasonable amount of
> > > > > time. I updated the patch to keep track of 3 numbers of repeats, and we
> > > > > consider that we got valid entropy once the new number of repeats is
> > > > > different from the last two.
> > > > > 
> > > > > So in the sequence above, e.g. for 7,8,7,8,8,7, at the point of the last
> > > > > one, we have old repeats 8 and 8, and the new repeat count 7, which in that
> > > > > context looks unique.
> > > > 
> > > > I was thinking that in 7,8,8 that 7 and 8 be the 2 least recent used
> > > > values not 8,8
> > > 
> > > Sure, that's probably doable too.
> > > 
> > > > that is, something like:
> > > > 
> > > > if (old2 == new) {
> > > >    FFSWAP(old,old2);
> > > 
> > > I don't see why we'd need to check this if clause at all, it seems to me
> > > that it's enough to have the "if (old != new)" case.
> > 
> > > If we have old2 == new,
> > > we'd just end up with old2 = old, and old = (previous old2 value) anyway.
> > 
> > It was intended to be a least recent used check with 2 entries
> > 
> > If we have a clock running and sample that in precise intervalls
> > lets say the clock runs at 1.9hz and we sample at 10hz we would get
> > 
> > clock:    0  0  0  0  0  0  1  1  1  1  1  2  2  2  2  2  3  3  3  3  3  3  4  4  4  4  4  5  5  5  5  5  6  6  6  6  6  7  7  7  7  7  7  8  8  8  8  8  9  9
> > difference:  0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  1  0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  1  0  0  0  0  1  0  0  0  0  0  1  0  0  0  0  1  0
> > 
> > Above adds no entropy after the initial entropy, this can be read forever
> > it will not improve randomness
> > 
> > here we have runs of repeated clock reads of 5,4,4,5,4,4,4,5,4
> > again we can read this as long as we want there is no entropy gained
> > so after a 5,4,4,4 if a 5 happens thats not breaking the pattern and should
> > not be counted as new entropy (if possible)
> 
> Yes, I get that intent.
> 
> It's just that your suggested pseudocode seems unnecessarily complex, or I'm
> missing something:
> 
> if (old2 == new) {
>     FFSWAP(old,old2);
> } else if (old != new) {
>     old2 = old;
>     old = new;
> }
> 
> If we have the sequence "5, 4, 4, 4, 4", followed by another "5", we have
> old2 == 5, old == 4, new == 5. Then we get the same end result (old2 == 4,
> old == 5) both if we execute the code you suggest above, and if we just
> execute this:
> 
> if (old != new) {
>     old2 = old;
>     old = new;
> }
> 
> Or is there something I'm missing? I don't see the need for the FFSWAP case.
> 
> As long as we check (new != old && new != old2) we should pick up actual
> deviation from the steady state but not the variance between two values.

Heres an example where the SWAP is needed:
     noswap swap
5 -> [x 5]  [x 5]
4 -> [5 4]  [5 4]
5 -> [5 4]  [4 5]
6 -> [4 6]  [5 6]
5 -> [6 5]  [6 5]

In the last case the 5 is in the old* when the swap was used but not
when it was not used

thx

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

Never trust a computer, one day, it may think you are the virus. -- Compn
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 195 bytes
Desc: not available
URL: <https://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20250212/0a181007/attachment.sig>