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

[Martin Storsjö]

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.

// Martin