[9front] [PATCH] libc: replace lrand's algorithm

[Eolien55 <eolien55@disroot.org>]

[-- 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);
}