[FFmpeg-devel] [PATCH v2 1/2] random_seed: Reorder if clauses for gathering entropy

[FFmpeg-devel] [PATCH v2 1/2] random_seed: Reorder if clauses for gathering entropy

[Martin Storsjö]

Make it easier to add more cases.

This should be a pure refactoring, with no functional changes.
---
 libavutil/random_seed.c | 19 +++++++++++--------
 1 file changed, 11 insertions(+), 8 deletions(-)

diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c
index 8a4e4f1fc0..ca084b40da 100644
--- a/libavutil/random_seed.c
+++ b/libavutil/random_seed.c
@@ -98,17 +98,20 @@ static uint32_t get_generic_seed(void)
 
     for (;;) {
         clock_t t = clock();
-        if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t) {
-            last_td = t - last_t;
-            buffer[i & 511] = 1664525*buffer[i & 511] + 1013904223 + (last_td % 3294638521U);
+        int incremented_i = 0;
+        int cur_td = t - last_t;
+        if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) < t) {
+            buffer[++i & 511] += cur_td % 3294638521U;
+            incremented_i = 1;
         } else {
-            last_td = t - last_t;
-            buffer[++i & 511] += last_td % 3294638521U;
-            if ((t - init_t) >= CLOCKS_PER_SEC>>5)
-                if (last_i && i - last_i > 4 || i - last_i > 64 || TEST && i - last_i > 8)
-                    break;
+            buffer[i & 511] = 1664525*buffer[i & 511] + 1013904223 + (cur_td % 3294638521U);
+        }
+        if (incremented_i && (t - init_t) >= CLOCKS_PER_SEC>>5) {
+            if (last_i && i - last_i > 4 || i - last_i > 64 || TEST && i - last_i > 8)
+                break;
         }
         last_t = t;
+        last_td = cur_td;
         if (!init_t)
             init_t = t;
     }
-- 
2.43.0

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

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

[Martin Storsjö]

On a Zen 5, on Ubuntu 24.04 (with CLOCKS_PER_SEC 1000000), the
value of clock() in this loop increments by 0 most of the time,
and when it does increment, it usually increments by 1 compared
to the previous round.

Due to the "last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t"
expression, we only manage to take one step forward in this loop
(incrementing i) if clock() increments by 2, while it incremented
by 0 in the previous iteration (last_td).

This is similar to the change done in
c4152fc42e480c41efb7f761b1bbe5f0bc43d5bc, to speed it up on
systems with very small CLOCKS_PER_SEC. However in this case,
CLOCKS_PER_SEC is still very large, but the machine is fast enough
to hit every clock increment repeatedly.

For this case, use the number of repetitions of each timer value
as entropy source; require a change in the number of repetitions
in order to proceed to the next buffer index.

This helps the fate-random-seed test to actually terminate within
a reasonable time on such a system (where it previously could hang,
running for many minutes).
---
 libavutil/random_seed.c | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c
index ca084b40da..adb7b1f717 100644
--- a/libavutil/random_seed.c
+++ b/libavutil/random_seed.c
@@ -83,6 +83,7 @@ static uint32_t get_generic_seed(void)
     static uint32_t buffer[512] = { 0 };
     unsigned char digest[20];
     uint64_t last_i = i;
+    int last_repeat = 0, cur_repeat = 0;
 
     av_assert0(sizeof(tmp) >= av_sha_size);
 
@@ -101,8 +102,21 @@ static uint32_t get_generic_seed(void)
         int incremented_i = 0;
         int cur_td = t - last_t;
         if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) < t) {
+            // If the timer incremented by more than 2*last_td at once,
+            // we may e.g. have had a context switch. If the timer resolution
+            // is high (CLOCKS_PER_SEC > 1000), require that the timer
+            // incremented by more than 1. If the timer resolution is low,
+            // it is enough that the timer incremented at all.
             buffer[++i & 511] += cur_td % 3294638521U;
             incremented_i = 1;
+        } else if (t != last_t && cur_repeat > 0 && last_repeat > 0 &&
+                   cur_repeat != last_repeat) {
+            // 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.
+            buffer[++i & 511] += (cur_repeat + last_repeat) % 3294638521U;
+            incremented_i = 1;
         } else {
             buffer[i & 511] = 1664525*buffer[i & 511] + 1013904223 + (cur_td % 3294638521U);
         }
@@ -110,6 +124,12 @@ static uint32_t get_generic_seed(void)
             if (last_i && i - last_i > 4 || i - last_i > 64 || TEST && i - last_i > 8)
                 break;
         }
+        if (t == last_t) {
+            cur_repeat++;
+        } else {
+            last_repeat = cur_repeat;
+            cur_repeat = 0;
+        }
         last_t = t;
         last_td = cur_td;
         if (!init_t)
-- 
2.43.0

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

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

[Michael Niedermayer]

[-- Attachment #1.1: Type: text/plain, Size: 3394 bytes --]

Hi Martin

On Thu, Feb 06, 2025 at 12:18:09AM +0200, Martin Storsjö wrote:
> On a Zen 5, on Ubuntu 24.04 (with CLOCKS_PER_SEC 1000000), the
> value of clock() in this loop increments by 0 most of the time,
> and when it does increment, it usually increments by 1 compared
> to the previous round.
> 
> Due to the "last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t"
> expression, we only manage to take one step forward in this loop
> (incrementing i) if clock() increments by 2, while it incremented
> by 0 in the previous iteration (last_td).
> 
> This is similar to the change done in
> c4152fc42e480c41efb7f761b1bbe5f0bc43d5bc, to speed it up on
> systems with very small CLOCKS_PER_SEC. However in this case,
> CLOCKS_PER_SEC is still very large, but the machine is fast enough
> to hit every clock increment repeatedly.
> 
> For this case, use the number of repetitions of each timer value
> as entropy source; require a change in the number of repetitions
> in order to proceed to the next buffer index.
> 
> This helps the fate-random-seed test to actually terminate within
> a reasonable time on such a system (where it previously could hang,
> running for many minutes).
> ---
>  libavutil/random_seed.c | 20 ++++++++++++++++++++
>  1 file changed, 20 insertions(+)
> 
> diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c
> index ca084b40da..adb7b1f717 100644
> --- a/libavutil/random_seed.c
> +++ b/libavutil/random_seed.c
> @@ -83,6 +83,7 @@ static uint32_t get_generic_seed(void)
>      static uint32_t buffer[512] = { 0 };
>      unsigned char digest[20];
>      uint64_t last_i = i;
> +    int last_repeat = 0, cur_repeat = 0;
>  
>      av_assert0(sizeof(tmp) >= av_sha_size);
>  
> @@ -101,8 +102,21 @@ static uint32_t get_generic_seed(void)
>          int incremented_i = 0;
>          int cur_td = t - last_t;
>          if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) < t) {
> +            // If the timer incremented by more than 2*last_td at once,
> +            // we may e.g. have had a context switch. If the timer resolution
> +            // is high (CLOCKS_PER_SEC > 1000), require that the timer
> +            // incremented by more than 1. If the timer resolution is low,
> +            // it is enough that the timer incremented at all.
>              buffer[++i & 511] += cur_td % 3294638521U;
>              incremented_i = 1;
> +        } else if (t != last_t && cur_repeat > 0 && last_repeat > 0 &&
> +                   cur_repeat != last_repeat) {
> +            // 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

thx

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

Nations do behave wisely once they have exhausted all other alternatives. 
-- Abba Eban

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

[-- Attachment #2: Type: text/plain, Size: 251 bytes --]

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

Re: [FFmpeg-devel] [PATCH v2 1/2] random_seed: Reorder if clauses for gathering entropy

[Michael Niedermayer]

[-- Attachment #1.1: Type: text/plain, Size: 1998 bytes --]

Hi

On Thu, Feb 06, 2025 at 12:18:08AM +0200, Martin Storsjö wrote:
> Make it easier to add more cases.
> 
> This should be a pure refactoring, with no functional changes.
> ---
>  libavutil/random_seed.c | 19 +++++++++++--------
>  1 file changed, 11 insertions(+), 8 deletions(-)
> 
> diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c
> index 8a4e4f1fc0..ca084b40da 100644
> --- a/libavutil/random_seed.c
> +++ b/libavutil/random_seed.c
> @@ -98,17 +98,20 @@ static uint32_t get_generic_seed(void)
>  
>      for (;;) {
>          clock_t t = clock();
> -        if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t) {
> -            last_td = t - last_t;
> -            buffer[i & 511] = 1664525*buffer[i & 511] + 1013904223 + (last_td % 3294638521U);
> +        int incremented_i = 0;
> +        int cur_td = t - last_t;
> +        if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) < t) {
> +            buffer[++i & 511] += cur_td % 3294638521U;
> +            incremented_i = 1;
>          } else {
> -            last_td = t - last_t;
> -            buffer[++i & 511] += last_td % 3294638521U;
> -            if ((t - init_t) >= CLOCKS_PER_SEC>>5)
> -                if (last_i && i - last_i > 4 || i - last_i > 64 || TEST && i - last_i > 8)
> -                    break;
> +            buffer[i & 511] = 1664525*buffer[i & 511] + 1013904223 + (cur_td % 3294638521U);
> +        }
> +        if (incremented_i && (t - init_t) >= CLOCKS_PER_SEC>>5) {
> +            if (last_i && i - last_i > 4 || i - last_i > 64 || TEST && i - last_i > 8)
> +                break;
>          }
>          last_t = t;
> +        last_td = cur_td;
>          if (!init_t)
>              init_t = t;
>      }

sure, if you prefer / if it makes chanegs easier

thx

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

I am the wisest man alive, for I know one thing, and that is that I know
nothing. -- Socrates

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

[-- Attachment #2: Type: text/plain, Size: 251 bytes --]

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

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

[Martin Storsjö]

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.

It's obviously not entirely unique in the wider context there, but it 
should cover for cases when we alternate between two numbers at least. 
It's of course not hard to make it look at an even longer history, 
although the conditional becomes a bit more unwieldy in that form.

// Martin

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

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

[Michael Niedermayer]

[-- Attachment #1.1: Type: text/plain, Size: 1827 bytes --]

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
that is, something like:

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

but again, iam not sure this will work or just need too much time to gather
enough entropy

thx

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

Some people wanted to paint the bikeshed green, some blue and some pink.
People argued and fought, when they finally agreed, only rust was left.

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

[-- Attachment #2: Type: text/plain, Size: 251 bytes --]

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".