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 BD51021F2D for ; Fri, 29 Mar 2024 09:17:00 +0100 (CET) Received: from layka.disroot.org ([178.21.23.139]) by 9front; Fri Mar 29 04:15:51 -0400 2024 Received: from localhost (localhost [127.0.0.1]) by disroot.org (Postfix) with ESMTP id EF4A140CF8 for <9front@9front.org>; Fri, 29 Mar 2024 09:15:48 +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 ViFTh79M7gxW for <9front@9front.org>; Fri, 29 Mar 2024 09:15:47 +0100 (CET) Date: Fri, 29 Mar 2024 09:15:46 +0100 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=disroot.org; s=mail; t=1711700147; bh=KdMTOfzXjDRZvQCXe8ctpOuudW+oMmfopUP8m7qIcy4=; h=Date:To:Subject:From; b=jqejIcOrlKUzXNEEH43UjlqYZFkpLsMoO5xK04R71wwpzKrq4dMKiiYgN3if5SJ7k zubqiW7mU5nVnaWGiJfkaCcIuY/zNq8tJNtdv+6JfasqPGA6G1VmxspIesUQziHySG Y+3UNPZAre/Qx/P3YbEBjSlziFSLWxNVaNpZhnajP5ELgiwmwvxuBwAP7yUQ60hhu/ S97fTmaoPnKOXIRI9X5pcEVqJxW05EywikujFt+7Kd8H8k+B1uwrWtYMmj1UkNkmzx S4Wk2Sz2DWQjK++uj24VVYQ6KErzwixbvTjUaetaMI5qlxaNsQJkMywvGqBSLIN8uu ir6jQqcp9scEQ== To: 9front@9front.org From: Eolien55 Message-Id: <2NVDMYHDK8IOX.2COQ9HEY8XZ1T@e55-lap.my.domain> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----_=_48785a2a076c30602a4f0e8e_=_" List-ID: <9front.9front.org> List-Help: X-Glyph: ➈ X-Bullshit: realtime out-scaling module interface Subject: [9front] [PATCH] libc: replace lrand's algorithm Reply-To: 9front@9front.org Precedence: bulk This is a multipart message in MIME format. ------_=_48785a2a076c30602a4f0e8e_=_ 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 ------_=_48785a2a076c30602a4f0e8e_=_ Content-Type: multipart/mixed; boundary="upas-krcwfakpwepmqqwhmnibzyuawt" Content-Disposition: inline This is a multi-part message in MIME format. --upas-krcwfakpwepmqqwhmnibzyuawt 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-krcwfakpwepmqqwhmnibzyuawt 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-krcwfakpwepmqqwhmnibzyuawt-- ------_=_48785a2a076c30602a4f0e8e_=_ 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); } ------_=_48785a2a076c30602a4f0e8e_=_--