1 /* 2 This is a maximally equidistributed combined Tausworthe generator 3 based on code from GNU Scientific Library 1.5 (30 Jun 2004) 4 5 x_n = (s1_n ^ s2_n ^ s3_n) 6 7 s1_{n+1} = (((s1_n & 4294967294) <<12) ^ (((s1_n <<13) ^ s1_n) >>19)) 8 s2_{n+1} = (((s2_n & 4294967288) << 4) ^ (((s2_n << 2) ^ s2_n) >>25)) 9 s3_{n+1} = (((s3_n & 4294967280) <<17) ^ (((s3_n << 3) ^ s3_n) >>11)) 10 11 The period of this generator is about 2^88. 12 13 From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe 14 Generators", Mathematics of Computation, 65, 213 (1996), 203--213. 15 16 This is available on the net from L'Ecuyer's home page, 17 18 http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps 19 ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/tausme.ps 20 21 There is an erratum in the paper "Tables of Maximally 22 Equidistributed Combined LFSR Generators", Mathematics of 23 Computation, 68, 225 (1999), 261--269: 24 http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps 25 26 ... the k_j most significant bits of z_j must be non- 27 zero, for each j. (Note: this restriction also applies to the 28 computer code given in [4], but was mistakenly not mentioned in 29 that paper.) 30 31 This affects the seeding procedure by imposing the requirement 32 s1 > 1, s2 > 7, s3 > 15. 33 34 */ 35 36 #include <string.h> 37 #include <assert.h> 38 #include "rand.h" 39 #include "../hash.h" 40 41 static inline int __seed(unsigned int x, unsigned int m) 42 { 43 return (x < m) ? x + m : x; 44 } 45 46 static void __init_rand(struct frand_state *state, unsigned int seed) 47 { 48 int cranks = 6; 49 50 #define LCG(x, seed) ((x) * 69069 ^ (seed)) 51 52 state->s1 = __seed(LCG((2^31) + (2^17) + (2^7), seed), 1); 53 state->s2 = __seed(LCG(state->s1, seed), 7); 54 state->s3 = __seed(LCG(state->s2, seed), 15); 55 56 while (cranks--) 57 __rand(state); 58 } 59 60 void init_rand(struct frand_state *state) 61 { 62 __init_rand(state, 1); 63 } 64 65 void init_rand_seed(struct frand_state *state, unsigned int seed) 66 { 67 __init_rand(state, seed); 68 } 69 70 void __fill_random_buf(void *buf, unsigned int len, unsigned long seed) 71 { 72 void *ptr = buf; 73 74 while (len) { 75 int this_len; 76 77 if (len >= sizeof(int64_t)) { 78 *((int64_t *) ptr) = seed; 79 this_len = sizeof(int64_t); 80 } else if (len >= sizeof(int32_t)) { 81 *((int32_t *) ptr) = seed; 82 this_len = sizeof(int32_t); 83 } else if (len >= sizeof(int16_t)) { 84 *((int16_t *) ptr) = seed; 85 this_len = sizeof(int16_t); 86 } else { 87 *((int8_t *) ptr) = seed; 88 this_len = sizeof(int8_t); 89 } 90 ptr += this_len; 91 len -= this_len; 92 seed *= GOLDEN_RATIO_PRIME; 93 seed >>= 3; 94 } 95 } 96 97 unsigned long fill_random_buf(struct frand_state *fs, void *buf, 98 unsigned int len) 99 { 100 unsigned long r = __rand(fs); 101 102 if (sizeof(int) != sizeof(long *)) 103 r *= (unsigned long) __rand(fs); 104 105 __fill_random_buf(buf, len, r); 106 return r; 107 } 108 109 void fill_pattern(void *p, unsigned int len, char *pattern, 110 unsigned int pattern_bytes) 111 { 112 switch (pattern_bytes) { 113 case 0: 114 assert(0); 115 break; 116 case 1: 117 memset(p, pattern[0], len); 118 break; 119 default: { 120 unsigned int i = 0, size = 0; 121 unsigned char *b = p; 122 123 while (i < len) { 124 size = pattern_bytes; 125 if (size > (len - i)) 126 size = len - i; 127 memcpy(b+i, pattern, size); 128 i += size; 129 } 130 break; 131 } 132 } 133 } 134 135 void __fill_random_buf_percentage(unsigned long seed, void *buf, 136 unsigned int percentage, 137 unsigned int segment, unsigned int len, 138 char *pattern, unsigned int pbytes) 139 { 140 unsigned int this_len; 141 142 if (percentage == 100) { 143 if (pbytes) 144 fill_pattern(buf, len, pattern, pbytes); 145 else 146 memset(buf, 0, len); 147 return; 148 } 149 150 if (segment > len) 151 segment = len; 152 153 while (len) { 154 /* 155 * Fill random chunk 156 */ 157 this_len = (segment * (100 - percentage)) / 100; 158 if (this_len > len) 159 this_len = len; 160 161 __fill_random_buf(buf, this_len, seed); 162 163 len -= this_len; 164 if (!len) 165 break; 166 buf += this_len; 167 168 if (this_len > len) 169 this_len = len; 170 else if (len - this_len <= sizeof(long)) 171 this_len = len; 172 173 if (pbytes) 174 fill_pattern(buf, this_len, pattern, pbytes); 175 else 176 memset(buf, 0, this_len); 177 178 len -= this_len; 179 buf += this_len; 180 } 181 } 182 183 unsigned long fill_random_buf_percentage(struct frand_state *fs, void *buf, 184 unsigned int percentage, 185 unsigned int segment, unsigned int len, 186 char *pattern, unsigned int pbytes) 187 { 188 unsigned long r = __rand(fs); 189 190 if (sizeof(int) != sizeof(long *)) 191 r *= (unsigned long) __rand(fs); 192 193 __fill_random_buf_percentage(r, buf, percentage, segment, len, 194 pattern, pbytes); 195 return r; 196 } 197
