Git Inbox Mirror of the ffmpeg-devel mailing list - see https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
 help / color / mirror / Atom feed
* [FFmpeg-devel] [PATCH v4 1/2] random_seed: Reorder if clauses for gathering entropy
@ 2025-02-12  9:29 Martin Storsjö
  2025-02-12  9:29 ` [FFmpeg-devel] [PATCH v4 2/2] random_seed: Improve behaviour with small timer increments with high precision timers Martin Storsjö
  0 siblings, 1 reply; 2+ messages in thread
From: Martin Storsjö @ 2025-02-12  9:29 UTC (permalink / raw)
  To: ffmpeg-devel; +Cc: Michael Niedermayer

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".

^ permalink raw reply	[flat|nested] 2+ messages in thread

* [FFmpeg-devel] [PATCH v4 2/2] random_seed: Improve behaviour with small timer increments with high precision timers
  2025-02-12  9:29 [FFmpeg-devel] [PATCH v4 1/2] random_seed: Reorder if clauses for gathering entropy Martin Storsjö
@ 2025-02-12  9:29 ` Martin Storsjö
  0 siblings, 0 replies; 2+ messages in thread
From: Martin Storsjö @ 2025-02-12  9:29 UTC (permalink / raw)
  To: ffmpeg-devel; +Cc: Michael Niedermayer

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).
---
v4: Keep a history of 2 old unique repeat counts, and require the
new count of repeats to differ from the previous 2 unique values
in order to count it as new entropy.
---
 libavutil/random_seed.c | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)

diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c
index ca084b40da..e08ab7b12e 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 repeats[3] = { 0 };
 
     av_assert0(sizeof(tmp) >= av_sha_size);
 
@@ -101,8 +102,23 @@ 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 && repeats[0] > 0 && repeats[1] > 0 &&
+                   repeats[2] > 0 && repeats[0] != repeats[1] &&
+                   repeats[0] != repeats[2]) {
+            // 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 we get a different number of
+            // repeats than the last two unique cases, count that as entropy
+            // and proceed to the next index.
+            buffer[++i & 511] += (repeats[0] + repeats[1] + repeats[2]) % 3294638521U;
+            incremented_i = 1;
         } else {
             buffer[i & 511] = 1664525*buffer[i & 511] + 1013904223 + (cur_td % 3294638521U);
         }
@@ -110,6 +126,16 @@ 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) {
+            repeats[0]++;
+        } else {
+            // If we got a new unique number of repeats, update the history.
+            if (repeats[0] != repeats[1]) {
+                repeats[2] = repeats[1];
+                repeats[1] = repeats[0];
+            }
+            repeats[0] = 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".

^ permalink raw reply	[flat|nested] 2+ messages in thread

end of thread, other threads:[~2025-02-12  9:30 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2025-02-12  9:29 [FFmpeg-devel] [PATCH v4 1/2] random_seed: Reorder if clauses for gathering entropy Martin Storsjö
2025-02-12  9:29 ` [FFmpeg-devel] [PATCH v4 2/2] random_seed: Improve behaviour with small timer increments with high precision timers Martin Storsjö

Git Inbox Mirror of the ffmpeg-devel mailing list - see https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

This inbox may be cloned and mirrored by anyone:

	git clone --mirror https://master.gitmailbox.com/ffmpegdev/0 ffmpegdev/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 ffmpegdev ffmpegdev/ https://master.gitmailbox.com/ffmpegdev \
		ffmpegdev@gitmailbox.com
	public-inbox-index ffmpegdev

Example config snippet for mirrors.


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git