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

[Martin Storsjö]

On Wed, 12 Feb 2025, Michael Niedermayer wrote:

> 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

Sorry, but your examples do not make sense or do not contain enough 
context (it does not include the initial states of the two old values, and 
it requires guesswork which ones of the two [x y] values is old and which 
one is old2).

But to be clear:

Please specify the initial values of the variables new, old and old2, for 
a case where

>> if (old2 == new) {
>>     FFSWAP(old,old2);
>> } else if (old != new) {
>>     old2 = old;
>>     old = new;
>> }

produces a different end result than

>> if (old != new) {
>>     old2 = old;
>>     old = new;
>> }

I claim that for any values of these variables, the end result is the 
same.

In any case, I'll send an update of the whole patchset - please do review 
it; I believe that it works as you want it to, and I would like to move 
forward with it.

// Martin