From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: <9front-bounces@9front.inri.net> X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.6 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI autolearn=ham autolearn_force=no version=3.4.4 Received: from 9front.inri.net (9front.inri.net [168.235.81.73]) by inbox.vuxu.org (Postfix) with ESMTP id 40D8024BBE for ; Fri, 29 Mar 2024 09:21:08 +0100 (CET) Received: from layka.disroot.org ([178.21.23.139]) by 9front; Fri Mar 29 04:19:56 -0400 2024 Received: from localhost (localhost [127.0.0.1]) by disroot.org (Postfix) with ESMTP id 9C44841921 for <9front@9front.org>; Fri, 29 Mar 2024 09:19:54 +0100 (CET) X-Virus-Scanned: SPAM Filter at disroot.org Received: from layka.disroot.org ([127.0.0.1]) by localhost (disroot.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id BnVxL62SoxlN for <9front@9front.org>; Fri, 29 Mar 2024 09:19:53 +0100 (CET) To: 9front@9front.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=disroot.org; s=mail; t=1711700393; bh=uFlrwXCB9CyDGLu78embJuEpGywv66oqGja17DRrA+E=; h=To:Subject:From:Date; b=jWp0hkufU2Lyro82HJaD7bXGZKit4lNxx4ZTWqp+NV85kiNN8rTynjA/tphsKP4je DlzcAT3pmnZdoxNAAJjaC+7sCa87TGao4DSya7T4tKM7wmFOgX0q9uJpzvBzlTl6Qq hD34lju3nOS8PlApmhZETyt1GOs/kKDSLnVNXF6A3GeEydisgB+g+p/n0chE6yRTAf 7VWQCdQfzwgfv+3GNfmzIexXuNRhZbhwpyey/SHTbGD1rdFjdBzNIf3qN52Jpv+85v GaAh1TI5a3dzicuhtc5DmJwnDViCXC62us3c5xoaKHtfS/QWLJuyB9Ccfv9GCmra9z UDFIcteTgluLw== From: Eolien55 Message-Id: <3LHKTP1HB4DYE.2X5KUF9RIVGEC@e55-lap.my.domain> Date: Fri, 29 Mar 2024 09:19:31 +0100 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----_=_132eadcc7106354a55fe5ce0_=_" List-ID: <9front.9front.org> List-Help: X-Glyph: ➈ X-Bullshit: generic non-blocking ActivityPub over SVG method property locator Subject: [9front] [PATCH] libc: replace lrand's algorithm Reply-To: 9front@9front.org Precedence: bulk This is a multipart message in MIME format. ------_=_132eadcc7106354a55fe5ce0_=_ Content-Type: text/plain; charset=UTF-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable 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-gene= rator ------_=_132eadcc7106354a55fe5ce0_=_ Content-Type: multipart/mixed; boundary="upas-oxvwuwmkefmimfhkcrqtdroijv" Content-Disposition: inline This is a multi-part message in MIME format. --upas-oxvwuwmkefmimfhkcrqtdroijv Content-Disposition: inline Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit 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 --upas-oxvwuwmkefmimfhkcrqtdroijv Content-Type: application/octet-stream Content-Disposition: attachment; filename="file.suspect" Content-Transfer-Encoding: quoted-printable =46rom 17a6a011ac9654e78a267474d534e8511dcd03fc Mon Sep 17 00:00:00 2001 =46rom: Elie Le Vaillant =44ate: Thu, 28 Mar 2024 23:03:08 +0100 =53ubject: [PATCH] libc: replace lrand's algorithm =0AThe previous algorithm (an ALFG) was big (4856 bytes), somewhat complex =2860 sloc), very expansive to seed, and had bad statistical properties[1].= =0AThis replaces it with PCG32-XSH-RR[2], which is smaller (4 bytes), simpl= =65r =2821 sloc), way less expansive to seed, a bit faster, and has better =73tatistical properties. =0A[1]: https://leviathansecurity.com/blog/attacking-gos-lagged-fibonacci-g= =65nerator =5B2]: https://pcg-random.org =2D-- =20sys/src/libc/port/lrand.c | 68 +++++++-------------------------------- =201 file changed, 12 insertions(+), 56 deletions(-) =0Adiff --git a/sys/src/libc/port/lrand.c b/sys/src/libc/port/lrand.c =69ndex 2ebb39622..ae08ed24e 100644 =2D-- a/sys/src/libc/port/lrand.c =2B++ b/sys/src/libc/port/lrand.c =40@ -2,82 +2,38 @@ =20#include =20= =20/* =2B * PCG32 XSH-RR variant =2B * constants taken from github.com/pcg-c =20 * algorithm by =2D * D. P. Mitchell & J. A. Reeds =2B * Melissa E. O=E2=80=99Neill =20 */ =20= =2D#define LEN 607 =2D#define TAP 273 =2D#define MASK 0x7fffffffL =2D#define A 48271 =2D#define M 2147483647 =2D#define Q 44488 =2D#define R 3399 =2D#define NORM (1.0/(1.0+MASK)) =2D =2Dstatic ulong rng_vec[LEN]; =2Dstatic ulong* rng_tap =3D rng_vec; =2Dstatic ulong* rng_feed =3D 0; =2Bstatic ulong state; =20static Lock lk; =20= =2Dstatic void =2Disrand(long seed) =2D{ =2D long lo, hi, x; =2D int i; =2D =2D rng_tap =3D rng_vec; =2D rng_feed =3D rng_vec+LEN-TAP; =2D seed =3D seed%M; =2D if(seed < 0) =2D seed +=3D M; =2D if(seed =3D=3D 0) =2D seed =3D 89482311; =2D x =3D seed; =2D /* =2D * Initialize by x[n+1] =3D 48271 * x[n] mod (2**31 - 1) =2D */ =2D for(i =3D -20; i < LEN; i++) { =2D hi =3D x / Q; =2D lo =3D x % Q; =2D x =3D A*lo - R*hi; =2D if(x < 0) =2D x +=3D M; =2D if(i >=3D 0) =2D rng_vec[i] =3D x; =2D } =2D} =2D =20void =20srand(long seed) =20{ =20 lock(&lk); =2D isrand(seed); =2B state =3D (ulong)seed; =20 unlock(&lk); =20} =20= =20long =20lrand(void) =20{ =2D ulong x; =2B u64int oldstate =3D state; =2B u32int r, x; =20= =20 lock(&lk); =20= =2D rng_tap--; =2D if(rng_tap < rng_vec) { =2D if(rng_feed =3D=3D 0) { =2D isrand(1); =2D rng_tap--; =2D } =2D rng_tap +=3D LEN; =2D } =2D rng_feed--; =2D if(rng_feed < rng_vec) =2D rng_feed +=3D LEN; =2D x =3D (*rng_feed + *rng_tap) & MASK; =2D *rng_feed =3D x; =2B state *=3D 747796405U; =2B state +=3D 2891336453U; =20= =20 unlock(&lk); =20= =2B r =3D oldstate >> (64 - 5); =2B x =3D (oldstate ^ (oldstate >> 18)) >> (32 - 5); =2B x =3D (x >> (-r & 31)) | (x << r); =20 return x; =20} =2D-=20 =32.44.0 =0A= --upas-oxvwuwmkefmimfhkcrqtdroijv-- ------_=_132eadcc7106354a55fe5ce0_=_ Content-Disposition: attachment; filename=bench.c Content-Type: text/x-c;charset=us-ascii Content-Transfer-Encoding: 7bit #include #include #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); } ------_=_132eadcc7106354a55fe5ce0_=_--