pd.if.org Git - liblfds/blob - liblfds/liblfds7.0.0/liblfds700/src/lfds700_misc/lfds700_misc_prng.c

   1 /***** includes *****/
   2 #include "lfds700_misc_internal.h"
   3
   4 /***** defines *****/
   5 #define LFDS700_PRNG_STATE_SIZE  16
   6
   7 /***** struct *****/
   8 struct lfds700_misc_prng_big_slow_high_quality_state
   9 {
  10   lfds700_pal_atom_t LFDS700_PAL_ALIGN(LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES)
  11     xorshift1024star_spinlock;
  12
  13   // TRD : must be a 32 bit signed int
  14   int
  15     xorshift1024star_index;
  16
  17   int long long unsigned
  18     xorshift1024star_state[LFDS700_PRNG_STATE_SIZE];
  19 };
  20
  21 /***** locals *****/
  22 struct lfds700_misc_prng_big_slow_high_quality_state
  23   pbshqs;
  24
  25 /***** private prototypes *****/
  26 static void lfds700_misc_prng_internal_hash_murmurhash3( int long long unsigned *murmurhash3_state );
  27 static void lfds700_misc_prng_internal_big_slow_high_quality_generate( struct lfds700_misc_prng_big_slow_high_quality_state *ps, lfds700_pal_uint_t *random_value );
  28
  29
  30
  31
  32
  33 /****************************************************************************/
  34 void lfds700_misc_prng_init( struct lfds700_misc_prng_state *ps )
  35 {
  36   LFDS700_PAL_ASSERT( ps != NULL );
  37
  38   /* TRD : we use the big, slow, high quality PRNG to generate the initial value
  39            for the small, fast, low qulity PRNG, which is used in exponential backoff
  40
  41            we need the load barrier to catch any changes to the backoff periods
  42   */
  43
  44   lfds700_misc_prng_internal_big_slow_high_quality_generate( &pbshqs, &ps->prng_state );
  45
  46   LFDS700_MISC_BARRIER_LOAD;
  47
  48   ps->local_copy_of_global_exponential_backoff_timeslot_length_in_loop_iterations_for_cas = lfds700_misc_globals.exponential_backoff_timeslot_length_in_loop_iterations_for_cas;
  49   ps->local_copy_of_global_exponential_backoff_timeslot_length_in_loop_iterations_for_dwcas = lfds700_misc_globals.exponential_backoff_timeslot_length_in_loop_iterations_for_dwcas;
  50
  51   return;
  52 }
  53
  54
  55
  56
  57
  58 /****************************************************************************/
  59 void lfds700_misc_prng_internal_big_slow_high_quality_init( int long long unsigned seed )
  60 {
  61   lfds700_pal_uint_t
  62     loop;
  63
  64   LFDS700_PAL_ASSERT( seed != 0 );   // TRD : a 0 seed causes all zeros in the entropy state, so is forbidden
  65
  66   pbshqs.xorshift1024star_spinlock = LFDS700_MISC_FLAG_LOWERED;
  67
  68   for( loop = 0 ; loop < LFDS700_PRNG_STATE_SIZE ; loop++ )
  69   {
  70     lfds700_misc_prng_internal_hash_murmurhash3( &seed );
  71     pbshqs.xorshift1024star_state[loop] = seed;
  72   }
  73
  74   pbshqs.xorshift1024star_index = 0;
  75
  76   return;
  77 }
  78
  79
  80
  81
  82
  83 /****************************************************************************/
  84 static void lfds700_misc_prng_internal_hash_murmurhash3( int long long unsigned *murmurhash3_state )
  85 {
  86   LFDS700_PAL_ASSERT( murmurhash3_state != NULL );
  87
  88         *murmurhash3_state ^= *murmurhash3_state >> 33;
  89         *murmurhash3_state *= 0xff51afd7ed558ccdULL;
  90         *murmurhash3_state ^= *murmurhash3_state >> 33;
  91         *murmurhash3_state *= 0xc4ceb9fe1a85ec53ULL;
  92         *murmurhash3_state ^= *murmurhash3_state >> 33;
  93
  94   return;
  95 }
  96
  97
  98
  99
 100
 101 /****************************************************************************/
 102 static void lfds700_misc_prng_internal_big_slow_high_quality_generate( struct lfds700_misc_prng_big_slow_high_quality_state *ps, lfds700_pal_uint_t *random_value )
 103 {
 104   char unsigned
 105     result;
 106
 107   int long long unsigned
 108     xs_temp_one,
 109     xs_temp_two;
 110
 111   lfds700_pal_atom_t
 112     compare = LFDS700_MISC_FLAG_LOWERED,
 113     exchange = LFDS700_MISC_FLAG_LOWERED;
 114
 115   LFDS700_PAL_ASSERT( ps != NULL );
 116   LFDS700_PAL_ASSERT( random_value != NULL );
 117
 118   // TRD : this is single-threaded code, on a per-state basis
 119   do
 120   {
 121     compare = LFDS700_MISC_FLAG_LOWERED;
 122     LFDS700_PAL_ATOMIC_CAS( &ps->xorshift1024star_spinlock, &compare, (lfds700_pal_atom_t) LFDS700_MISC_FLAG_RAISED, LFDS700_MISC_CAS_STRENGTH_STRONG, result );
 123   }
 124   while( result == 0 );
 125
 126   // TRD : xorshift1024* code from here; http://xorshift.di.unimi.it/xorshift1024star.c
 127
 128   xs_temp_one = ps->xorshift1024star_state[ ps->xorshift1024star_index ];
 129   ps->xorshift1024star_index = ( ps->xorshift1024star_index + 1 ) & 15;
 130   xs_temp_two = ps->xorshift1024star_state[ ps->xorshift1024star_index ];
 131
 132   xs_temp_two ^= xs_temp_two << 31;
 133   xs_temp_two ^= xs_temp_two >> 11;
 134   xs_temp_one ^= xs_temp_one >> 30;
 135
 136   ps->xorshift1024star_state[ ps->xorshift1024star_index ] = xs_temp_one ^ xs_temp_two;
 137
 138   *random_value = (lfds700_pal_uint_t) ( ps->xorshift1024star_state[ ps->xorshift1024star_index ] * 1181783497276652981LL );
 139
 140   LFDS700_PAL_ATOMIC_EXCHANGE( &ps->xorshift1024star_spinlock, &exchange );
 141
 142   return;
 143 }
 144