Changeset 2dcd80a for libcfa/src/bits

Timestamp:

Dec 14, 2022, 12:23:42 PM (3 years ago)

Author:

caparson <caparson@…>

Branches:

ADT, ast-experimental, master

Children:

441a6a7

Parents:

7d9598d8 (diff), d8bdf13 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:

• libcfa/src/bits/random.hfa (modified) (7 diffs)

libcfa/src/bits/random.hfa

@@ -10 +10 @@
 // Created On       : Fri Jan 14 07:18:11 2022
 // Last Modified By : Peter A. Buhr
-// Last Modified On : Fri Jan 14 07:18:58 2022
-// Update Count     : 1
+// Last Modified On : Sun Dec 11 18:43:58 2022
+// Update Count     : 171
 // 
 
@@ -18 +18 @@
 #include <stdint.h>
 
-// Pipelined to allow out-of-order overlap with reduced dependencies. Critically, the current random state is returned
-// (copied), and then compute and store the next random value.
-
-#if defined(__SIZEOF_INT128__)
-//--------------------------------------------------
+#define GLUE2( x, y ) x##y
+#define GLUE( x, y ) GLUE2( x, y )
+
+// Set default PRNG for architecture size.
+#ifdef __x86_64__                                                                               // 64-bit architecture
+        // 64-bit generators
+        #define LEHMER64
+        //#define XORSHIFT_12_25_27
+        //#define XOSHIRO256PP
+        //#define KISS_64
+
+        // 32-bit generators
+        #define XORSHIFT_6_21_7
+        //#define XOSHIRO128PP
+#else                                                                                                   // 32-bit architecture
+        // 64-bit generators
+        #define XORSHIFT_13_7_17
+
+        // 32-bit generators
+        #define XORSHIFT_6_21_7
+#endif // __x86_64__
+
+// Define C/CFA PRNG name and random-state.
+
+// SKULLDUGGERY: typedefs name struct and typedef with the same name to deal with CFA typedef numbering problem.
+
+#ifdef XOSHIRO256PP
+#define PRNG_NAME_64 xoshiro256pp
+#define PRNG_STATE_64_T GLUE(PRNG_NAME_64,_t)
+typedef struct PRNG_STATE_64_T { uint64_t s[4]; } PRNG_STATE_64_T;
+#endif // XOSHIRO256PP
+
+#ifdef XOSHIRO128PP
+#define PRNG_NAME_32 xoshiro128pp
+#define PRNG_STATE_32_T GLUE(PRNG_NAME_32,_t)
+typedef struct PRNG_STATE_32_T { uint32_t s[4]; } PRNG_STATE_32_T;
+#endif // XOSHIRO128PP
+
+#ifdef LEHMER64
+#define PRNG_NAME_64 lehmer64
+#define PRNG_STATE_64_T __uint128_t
+#endif // LEHMER64
+
+#ifdef WYHASH64
+#define PRNG_NAME_64 wyhash64
+#define PRNG_STATE_64_T uint64_t
+#endif // LEHMER64
+
+#ifdef XORSHIFT_13_7_17
+#define PRNG_NAME_64 xorshift_13_7_17
+#define PRNG_STATE_64_T uint64_t
+#endif // XORSHIFT_13_7_17
+
+#ifdef XORSHIFT_6_21_7
+#define PRNG_NAME_32 xorshift_6_21_7
+#define PRNG_STATE_32_T uint32_t
+#endif // XORSHIFT_6_21_7
+
+#ifdef XORSHIFT_12_25_27
+#define PRNG_NAME_64 xorshift_12_25_27
+#define PRNG_STATE_64_T uint64_t
+#endif // XORSHIFT_12_25_27
+
+#ifdef KISS_64
+#define PRNG_NAME_64 kiss_64
+#define PRNG_STATE_64_T GLUE(PRNG_NAME_64,_t)
+typedef struct PRNG_STATE_64_T { uint64_t z, w, jsr, jcong; } PRNG_STATE_64_T;
+#endif // KISS_^64
+
+#ifdef XORWOW
+#define PRNG_NAME_32 xorwow
+#define PRNG_STATE_32_T GLUE(PRNG_NAME_32,_t)
+typedef struct PRNG_STATE_32_T { uint32_t a, b, c, d, counter; } PRNG_STATE_32_T;
+#endif // XOSHIRO128PP
+
+#define PRNG_SET_SEED_64 GLUE(PRNG_NAME_64,_set_seed)
+#define PRNG_SET_SEED_32 GLUE(PRNG_NAME_32,_set_seed)
+
+
+// Default PRNG used by runtime.
+#ifdef __x86_64__                                                                               // 64-bit architecture
+#define PRNG_NAME PRNG_NAME_64
+#define PRNG_STATE_T PRNG_STATE_64_T
+#else                                                                                                   // 32-bit architecture
+#define PRNG_NAME PRNG_NAME_32
+#define PRNG_STATE_T PRNG_STATE_32_T
+#endif // __x86_64__
+
+#define PRNG_SET_SEED GLUE(PRNG_NAME,_set_seed)
+
+
+// ALL PRNG ALGORITHMS ARE OPTIMIZED SO THAT THE PRNG LOGIC CAN HAPPEN IN PARALLEL WITH THE USE OF THE RESULT.
+// Therefore, the set_seed routine primes the PRNG by calling it with the state so the seed is not return as the
+// first random value.
+
+#ifdef __cforall                                                                                // don't include in C code (invoke.h)
+
+// https://prng.di.unimi.it/xoshiro256starstar.c
+//
+// This is xoshiro256++ 1.0, one of our all-purpose, rock-solid generators.  It has excellent (sub-ns) speed, a state
+// (256 bits) that is large enough for any parallel application, and it passes all tests we are aware of.
+//
+// For generating just floating-point numbers, xoshiro256+ is even faster.
+//
+// The state must be seeded so that it is not everywhere zero. If you have a 64-bit seed, we suggest to seed a
+// splitmix64 generator and use its output to fill s.
+
+#ifndef XOSHIRO256PP
+typedef struct xoshiro256pp_t { uint64_t s[4]; } xoshiro256pp_t;
+#endif // ! XOSHIRO256PP
+
+static inline uint64_t xoshiro256pp( xoshiro256pp_t & rs ) with(rs) {
+        inline uint64_t rotl(const uint64_t x, int k) {
+                return (x << k) | (x >> (64 - k));
+        } // rotl
+
+        const uint64_t result = rotl( s[0] + s[3], 23 ) + s[0];
+        const uint64_t t = s[1] << 17;
+
+        s[2] ^= s[0];
+        s[3] ^= s[1];
+        s[1] ^= s[2];
+        s[0] ^= s[3];
+        s[2] ^= t;
+        s[3] = rotl( s[3], 45 );
+        return result;
+} // xoshiro256pp
+
+static inline void xoshiro256pp_set_seed( xoshiro256pp_t & state,  uint64_t seed ) {
+        state = (xoshiro256pp_t){ {seed, seed, seed, seed} };
+        xoshiro256pp( state );
+} // xoshiro256pp_set_seed
+
+// https://prng.di.unimi.it/xoshiro128plusplus.c
+//
+// This is xoshiro128++ 1.0, one of our 32-bit all-purpose, rock-solid generators. It has excellent speed, a state size
+// (128 bits) that is large enough for mild parallelism, and it passes all tests we are aware of.
+//
+// For generating just single-precision (i.e., 32-bit) floating-point numbers, xoshiro128+ is even faster.
+//
+// The state must be seeded so that it is not everywhere zero.
+
+#ifndef XOSHIRO128PP
+typedef struct xoshiro128pp_t { uint32_t s[4]; } xoshiro128pp_t;
+#endif // ! XOSHIRO128PP
+
+static inline uint32_t xoshiro128pp( xoshiro128pp_t & rs ) with(rs) {
+        inline uint32_t rotl( const uint32_t x, int k ) {
+                return (x << k) | (x >> (32 - k));
+        } // rotl
+
+        const uint32_t result = rotl( s[0] + s[3], 7 ) + s[0];
+        const uint32_t t = s[1] << 9;
+
+        s[2] ^= s[0];
+        s[3] ^= s[1];
+        s[1] ^= s[2];
+        s[0] ^= s[3];
+        s[2] ^= t;
+        s[3] = rotl( s[3], 11 );
+        return result;
+} // xoshiro128pp
+
+static inline void xoshiro128pp_set_seed( xoshiro128pp_t & state, uint32_t seed ) {
+        state = (xoshiro128pp_t){ {seed, seed, seed, seed} };
+        xoshiro128pp( state );                                                          // prime
+} // xoshiro128pp_set_seed
+
+#ifdef __SIZEOF_INT128__
+        // Pipelined to allow out-of-order overlap with reduced dependencies. Critically, the current random state is
+        // returned (copied), and then compute and store the next random value.
+        //--------------------------------------------------
         static inline uint64_t lehmer64( __uint128_t & state ) {
                 __uint128_t ret = state;
                 state *= 0xda942042e4dd58b5;
                 return ret >> 64;
-        }
-
-//--------------------------------------------------
+        } // lehmer64
+
+        static inline void lehmer64_set_seed( __uint128_t & state, uint64_t seed ) {
+                state = seed;
+                lehmer64( state );
+        } // lehmer64_set_seed
+
+        //--------------------------------------------------
         static inline uint64_t wyhash64( uint64_t & state ) {
-                state += 0x60bee2bee120fc15;
+                uint64_t ret = state;
+                state += 0x_60be_e2be_e120_fc15;
                 __uint128_t tmp;
-                tmp = (__uint128_t) state * 0xa3b195354a39b70d;
+                tmp = (__uint128_t) ret * 0x_a3b1_9535_4a39_b70d;
                 uint64_t m1 = (tmp >> 64) ^ tmp;
-                tmp = (__uint128_t)m1 * 0x1b03738712fad5c9;
+                tmp = (__uint128_t)m1 * 0x_1b03_7387_12fa_d5c9;
                 uint64_t m2 = (tmp >> 64) ^ tmp;
                 return m2;
-        }
-#endif
+        } // wyhash64
+
+        static inline void wyhash64_set_seed( uint64_t & state, uint64_t seed ) {
+                state = seed;
+                wyhash64( state );                                                              // prime
+        } // wyhash64_set_seed
+#endif // __SIZEOF_INT128__
 
 //--------------------------------------------------
@@ -48 +226 @@
         state ^= state << 17;
         return ret;
-}
-
-//--------------------------------------------------
+} // xorshift_13_7_17
+
+static inline void xorshift_13_7_17_set_seed( uint64_t & state, uint64_t seed ) {
+        state = seed;
+        xorshift_13_7_17( state );                                                      // prime
+} // xorshift_13_7_17_set_seed
+
+//--------------------------------------------------
+// Marsaglia shift-XOR PRNG with thread-local state
+// Period is 4G-1
+// 0 is absorbing and must be avoided
+// Low-order bits are not particularly random
 static inline uint32_t xorshift_6_21_7( uint32_t & state ) {
         uint32_t ret = state;
@@ -59 +246 @@
 } // xorshift_6_21_7
 
-//--------------------------------------------------
-typedef struct {
-  uint32_t a, b, c, d;
-  uint32_t counter;
-} xorwow__state_t;
-
-// The state array must be initialized to not be all zero in the first four words.
-static inline uint32_t xorwow( xorwow__state_t & state ) {
+static inline void xorshift_6_21_7_set_seed( uint32_t & state, uint32_t seed ) {
+        state = seed;
+        xorshift_6_21_7( state );                                                       // prime
+} // xorshift_6_21_7_set_seed
+
+//--------------------------------------------------
+// The state must be seeded with a nonzero value.
+static inline uint64_t xorshift_12_25_27( uint64_t & state ) {
+        uint64_t ret = state;
+        state ^= state >> 12;
+        state ^= state << 25;
+        state ^= state >> 27;
+        return ret * 0x_2545_F491_4F6C_DD1D;
+} // xorshift_12_25_27
+
+static inline void xorshift_12_25_27_set_seed( uint64_t & state, uint64_t seed ) {
+        state = seed;
+        xorshift_12_25_27( state );                                                     // prime
+} // xorshift_12_25_27_set_seed
+
+//--------------------------------------------------
+// The state must be seeded with a nonzero value.
+#ifndef KISS_64
+typedef struct kiss_64_t { uint64_t z, w, jsr, jcong; } kiss_64_t;
+#endif // ! KISS_64
+
+static inline uint64_t kiss_64( kiss_64_t & state ) with(state) {
+        kiss_64_t ret = state;
+        z = 36969 * (z & 65535) + (z >> 16);
+        w = 18000 * (w & 65535) + (w >> 16);
+        jsr ^= (jsr << 17);
+        jsr ^= (jsr << 13);
+        jsr ^= (jsr << 5);
+        jcong = 69069 * jcong + 1234567;
+        return (((ret.z << 16) + ret.w) ^ ret.jcong) + ret.jsr;
+} // kiss_64
+
+static inline void kiss_64_set_seed( kiss_64_t & state, uint64_t seed ) with(state) {
+        z = 1; w = 1; jsr = 4; jcong = seed;
+        kiss_64( state );                                                                       // prime
+} // kiss_64_set_seed
+
+//--------------------------------------------------
+// The state array must be initialized to non-zero in the first four words.
+#ifndef XORWOW
+typedef struct xorwow_t { uint32_t a, b, c, d, counter; } xorwow_t;
+#endif // ! XORWOW
+
+static inline uint32_t xorwow( xorwow_t & state ) with(state) {
         // Algorithm "xorwow" from p. 5 of Marsaglia, "Xorshift RNGs".
-        uint32_t ret = state.a + state.counter;
-        uint32_t t = state.d;
-
-        uint32_t const s = state.a;
-        state.d = state.c;
-        state.c = state.b;
-        state.b = s;
+        uint32_t ret = a + counter;
+        uint32_t t = d;
+
+        uint32_t const s = a;
+        d = c;
+        c = b;
+        b = s;
 
         t ^= t >> 2;
         t ^= t << 1;
         t ^= s ^ (s << 4);
-        state.a = t;
-
-        state.counter += 362437;
+        a = t;
+        counter += 362437;
         return ret;
-}
-
-//--------------------------------------------------
-static inline uint32_t LCG( uint32_t & state ) {                // linear congruential generator
-        uint32_t ret = state;
-        state = 36969 * (state & 65535) + (state >> 16);        // 36969 is NOT prime! No not change it!
-        return ret;
-} // LCG
-
-//--------------------------------------------------
+} // xorwow
+
+static inline void xorwow_set_seed( xorwow_t & state, uint32_t seed ) {
+        state = (xorwow_t){ seed, seed, seed, seed, 0 };
+        xorwow( state );                                                                        // prime
+} // xorwow_set_seed
+
+//--------------------------------------------------
+// Used in __tls_rand_fwd
 #define M  (1_l64u << 48_l64u)
 #define A  (25214903917_l64u)
@@ -103 +329 @@
         state = (A * state + C) & (M - 1);
         return state >> D;
-}
+} // LCGBI_fwd
 
 static inline uint32_t LCGBI_bck( uint64_t & state ) {
@@ -109 +335 @@
         state = AI * (state - C) & (M - 1);
         return r;
-}
+} // LCGBI_bck
 
 #undef M
@@ -116 +342 @@
 #undef C
 #undef D
+
+#endif // __cforall