From: Eolien55 <eolien55@disroot.org>
To: 9front@9front.org
Subject: [9front] [PATCH] libc: replace lrand's algorithm
Date: Fri, 29 Mar 2024 09:15:46 +0100 [thread overview]
Message-ID: <2NVDMYHDK8IOX.2COQ9HEY8XZ1T@e55-lap.my.domain> (raw)
[-- Attachment #1: Type: text/plain, Size: 953 bytes --]
Hello,
The current lrand's algorithm is quite suboptimal.
After benchmarking, we find:
Current algorithm:
repeated srand with different values: 820.740000
repeated lrand: 643.880000
Proposed algorithm (PCG32-XSH-RR[1]):
repeated srand with different valudes: 1.920000
repeated lrand: 600.590000
I've attached the benchmark code for reproducibility.
Though the lrand calls performance aren't themselves
all that bad, the design of the algorithm is not very
good. It has 4856 bytes of state (vs 4 bytes for PCG),
is very expensive to seed, as the benchmarks show
(because it actually uses an other PRNG to generate a
somewhat random state) and has bad statistical properties.
See [2] for a more detailed rationale and supplementary
materials on why this specific algorithm is suboptimal.
Regards,
Elie Le Vaillant
[1]: https://pcg-random.org
[2]: https://leviathansecurity.com/blog/attacking-gos-lagged-fibonacci-generator
[-- Attachment #2.1: Type: text/plain, Size: 376 bytes --]
from postmaster@9front:
The following attachment had content that we can't
prove to be harmless. To avoid possible automatic
execution, we changed the content headers.
The original header was:
Content-Disposition: attachment;
filename*0*=UTF-8''0001-libc-replace-lrand-s-algorithm.patch
Content-Type: text/x-diff;charset=utf-8
Content-Transfer-Encoding: quoted-printable
[-- Attachment #2.2: file.suspect --]
[-- Type: application/octet-stream, Size: 2585 bytes --]
From 17a6a011ac9654e78a267474d534e8511dcd03fc Mon Sep 17 00:00:00 2001
From: Elie Le Vaillant <eolien55@disroot.org>
Date: Thu, 28 Mar 2024 23:03:08 +0100
Subject: [PATCH] libc: replace lrand's algorithm
The previous algorithm (an ALFG) was big (4856 bytes), somewhat complex
(60 sloc), very expansive to seed, and had bad statistical properties[1].
This replaces it with PCG32-XSH-RR[2], which is smaller (4 bytes), simpler
(21 sloc), way less expansive to seed, a bit faster, and has better
statistical properties.
[1]: https://leviathansecurity.com/blog/attacking-gos-lagged-fibonacci-generator
[2]: https://pcg-random.org
---
sys/src/libc/port/lrand.c | 68 +++++++--------------------------------
1 file changed, 12 insertions(+), 56 deletions(-)
diff --git a/sys/src/libc/port/lrand.c b/sys/src/libc/port/lrand.c
index 2ebb39622..ae08ed24e 100644
--- a/sys/src/libc/port/lrand.c
+++ b/sys/src/libc/port/lrand.c
@@ -2,82 +2,38 @@
#include <libc.h>
/*
+ * PCG32 XSH-RR variant
+ * constants taken from github.com/pcg-c
* algorithm by
- * D. P. Mitchell & J. A. Reeds
+ * Melissa E. O’Neill
*/
-#define LEN 607
-#define TAP 273
-#define MASK 0x7fffffffL
-#define A 48271
-#define M 2147483647
-#define Q 44488
-#define R 3399
-#define NORM (1.0/(1.0+MASK))
-
-static ulong rng_vec[LEN];
-static ulong* rng_tap = rng_vec;
-static ulong* rng_feed = 0;
+static ulong state;
static Lock lk;
-static void
-isrand(long seed)
-{
- long lo, hi, x;
- int i;
-
- rng_tap = rng_vec;
- rng_feed = rng_vec+LEN-TAP;
- seed = seed%M;
- if(seed < 0)
- seed += M;
- if(seed == 0)
- seed = 89482311;
- x = seed;
- /*
- * Initialize by x[n+1] = 48271 * x[n] mod (2**31 - 1)
- */
- for(i = -20; i < LEN; i++) {
- hi = x / Q;
- lo = x % Q;
- x = A*lo - R*hi;
- if(x < 0)
- x += M;
- if(i >= 0)
- rng_vec[i] = x;
- }
-}
-
void
srand(long seed)
{
lock(&lk);
- isrand(seed);
+ state = (ulong)seed;
unlock(&lk);
}
long
lrand(void)
{
- ulong x;
+ u64int oldstate = state;
+ u32int r, x;
lock(&lk);
- rng_tap--;
- if(rng_tap < rng_vec) {
- if(rng_feed == 0) {
- isrand(1);
- rng_tap--;
- }
- rng_tap += LEN;
- }
- rng_feed--;
- if(rng_feed < rng_vec)
- rng_feed += LEN;
- x = (*rng_feed + *rng_tap) & MASK;
- *rng_feed = x;
+ state *= 747796405U;
+ state += 2891336453U;
unlock(&lk);
+ r = oldstate >> (64 - 5);
+ x = (oldstate ^ (oldstate >> 18)) >> (32 - 5);
+ x = (x >> (-r & 31)) | (x << r);
return x;
}
--
2.44.0
[-- Attachment #3: bench.c --]
[-- Type: text/x-c, Size: 567 bytes --]
#include <u.h>
#include <libc.h>
#define CLOCKS_PER_SEC 1000000L
void
main(int argc, char *argv[])
{
long start;
long newseed = time(0);
double elapsed;
start = clock();
for(long i = 0; i < 0xffffff; i++) {
srand(newseed);
newseed = lrand();
}
elapsed = ((double)(clock() - start))/(double)CLOCKS_PER_SEC;
print("repeated srand with different values: %f\n", elapsed);
start = clock();
for(long i = 0; i < 0xffffffff; i++) {
lrand();
}
elapsed = ((double)(clock() - start))/(double)CLOCKS_PER_SEC;
print("repeated lrand: %f\n", elapsed);
}
next reply other threads:[~2024-03-29 8:17 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-03-29 8:15 Eolien55 [this message]
2024-03-29 8:19 Eolien55
2024-03-29 12:39 ` qwx
2024-03-29 16:02 ` Eolien55
2024-04-01 15:47 ` qwx
2024-04-02 14:37 ` Eolien55
2024-04-02 14:52 ` Stanley Lieber
2024-04-02 20:18 ` Eolien55
2024-04-03 9:07 ` qwx
2024-04-03 19:50 ` Ori Bernstein
2024-04-03 19:54 ` Ori Bernstein
2024-04-04 21:00 ` Eolien55
2024-04-20 12:46 ` cinap_lenrek
2024-04-20 12:58 ` cinap_lenrek
2024-04-20 13:01 ` cinap_lenrek
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=2NVDMYHDK8IOX.2COQ9HEY8XZ1T@e55-lap.my.domain \
--to=eolien55@disroot.org \
--cc=9front@9front.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).