Index: doc/driver/invocation =================================================================== --- doc/driver/invocation (Revision 2461) +++ doc/driver/invocation (Arbeitskopie) @@ -254,7 +254,15 @@ --y|--yydebug Enable debugging of the LPC compiler. Only available if compiled with YYDEBUG. - + + --randomdevice + Chooses the source of the seed for the random number generator. + Default is /dev/urandom, Fall-back if is not readable is + the system clock. If you want to seed the PRNG with a specific seed, + you can use a filename with the seed and give it here instead of using + --random-seed. + (Note: the last one of --randominit and --random-seed wins!) + --random-seed Seed value for the random number generator. If not given, the driver chooses a seed value on its own. @@ -343,3 +351,4 @@ LDMud 3.3.672/3.2.11 added --tls-trustfile, --tls-trustdirectory. LDMud 3.3.677 added --max-mapping-keys. LDMud 3.3.714/3.2.15 added --tls-crlfile, --tls-crldirectory. + LDMud 3.3.x added --randominit. Index: src/random/FILES.txt =================================================================== --- src/random/FILES.txt (Revision 0) +++ src/random/FILES.txt (Revision 0) @@ -0,0 +1,21 @@ +This archive contails following directories and files. + +TOP DIRECTORY +FILES.txt: This file. +LICENSE.txt: License file. +CHANGE-LOG.txt: Change log file. +SFMT.h: Header file. +SFMT-params.h: parameter file which controls various Mersenne expornent +params607.h: parameters for period of 2^{607}-1 +params1279.h: parameters for period of 2^{1279}-1 +params2281.h: parameters for period of 2^{2281}-1 +params4253.h: parameters for period of 2^{4253}-1 +params11213.h: parameters for period of 2^{11213}-1 +params19937.h: parameters for period of 2^{19937}-1 +params44497.h: parameters for period of 2^{44497}-1 +params86243.h: parameters for period of 2^{86243}-1 +params132049.h: parameters for period of 2^{132049}-1 +params216091.h: parameters for period of 2^{216091}-1 +SFMT.c: C code for standard C (c99) and unix like systems. +SFMT-alti.h: C code optimized for PowerPC AltiVec. +SFMT-sse2.h: C code optimized for intel SSE2. Index: src/random/SFMT-params.h =================================================================== --- src/random/SFMT-params.h (Revision 0) +++ src/random/SFMT-params.h (Revision 0) @@ -0,0 +1,97 @@ +#ifndef SFMT_PARAMS_H +#define SFMT_PARAMS_H + +#if !defined(MEXP) +#ifdef __GNUC__ + #warning "MEXP is not defined. I assume MEXP is 19937." +#endif + #define MEXP 19937 +#endif +/*----------------- + BASIC DEFINITIONS + -----------------*/ +/** Mersenne Exponent. The period of the sequence + * is a multiple of 2^MEXP-1. + * #define MEXP 19937 */ +/** SFMT generator has an internal state array of 128-bit integers, + * and N is its size. */ +#define N (MEXP / 128 + 1) +/** N32 is the size of internal state array when regarded as an array + * of 32-bit integers.*/ +#define N32 (N * 4) +/** N64 is the size of internal state array when regarded as an array + * of 64-bit integers.*/ +#define N64 (N * 2) + +/*---------------------- + the parameters of SFMT + following definitions are in paramsXXXX.h file. + ----------------------*/ +/** the pick up position of the array. +#define POS1 122 +*/ + +/** the parameter of shift left as four 32-bit registers. +#define SL1 18 + */ + +/** the parameter of shift left as one 128-bit register. + * The 128-bit integer is shifted by (SL2 * 8) bits. +#define SL2 1 +*/ + +/** the parameter of shift right as four 32-bit registers. +#define SR1 11 +*/ + +/** the parameter of shift right as one 128-bit register. + * The 128-bit integer is shifted by (SL2 * 8) bits. +#define SR2 1 +*/ + +/** A bitmask, used in the recursion. These parameters are introduced + * to break symmetry of SIMD. +#define MSK1 0xdfffffefU +#define MSK2 0xddfecb7fU +#define MSK3 0xbffaffffU +#define MSK4 0xbffffff6U +*/ + +/** These definitions are part of a 128-bit period certification vector. +#define PARITY1 0x00000001U +#define PARITY2 0x00000000U +#define PARITY3 0x00000000U +#define PARITY4 0xc98e126aU +*/ + +#if MEXP == 607 + #include "SFMT-params607.h" +#elif MEXP == 1279 + #include "SFMT-params1279.h" +#elif MEXP == 2281 + #include "SFMT-params2281.h" +#elif MEXP == 4253 + #include "SFMT-params4253.h" +#elif MEXP == 11213 + #include "SFMT-params11213.h" +#elif MEXP == 19937 + #include "SFMT-params19937.h" +#elif MEXP == 44497 + #include "SFMT-params44497.h" +#elif MEXP == 86243 + #include "SFMT-params86243.h" +#elif MEXP == 132049 + #include "SFMT-params132049.h" +#elif MEXP == 216091 + #include "SFMT-params216091.h" +#else +#ifdef __GNUC__ + #error "MEXP is not valid." + #undef MEXP +#else + #undef MEXP +#endif + +#endif + +#endif /* SFMT_PARAMS_H */ Index: src/random/CHANGE-LOG.txt =================================================================== --- src/random/CHANGE-LOG.txt (Revision 0) +++ src/random/CHANGE-LOG.txt (Revision 0) @@ -0,0 +1,55 @@ +ver 1.3.3 +------- +change condition compile of do_recursion in SFMT.c + +ver 1.3.2 +------- +bug fix to_res53_mix and genrand_res53_mix. + +ver 1.3.1 +------- +gcc compile option changed form -O9 to -O3. +add functions genrand_res53_mix and to_res53_mix. +bug fix about definition of ALWAYS_INLINE. +add new definition PRE_ALWAYS for MSC. + +ver 1.3 +------- +bug fixed: -DONLY64 without -DBIG_ENIAN64 had been generating +wrong sequence. +bug fixed: There is no documentation about BIG_ENDIAN64. +add automatic endian check by __BIG_ENDIAN__ predefined macro. +bug fixed: change == in check.sh to = +add SFMT-params216091.h +add AltiVec parameter format for systems which are not osx. +change Makefile for systems which are not osx and support AltiVec. +change sample2 of howto-compile for Free BSD. +change source files for BORLANDC and Visual Studio. +change period certification code more smart. +add params directory. + +ver 1.2.1 +------- +Fix typo in SFMT-alti.c SFMT-sse2.c +marge SFMT-alti.c and SFMT-alti.h into SFMT-alti.h +marge SFMT-sse2.c and SFMT-sse2.h into SFMT-sse2.h +This version is not released. + +ver 1.2 +------- +Support many periods: 2^{607}, 2^{1279}, 2^{2281}, 2^{4253}, 2^{11213}, +2^{19937}, 2^{44497}, 2^{86243}, 2^{132049} +Fix typo in LICENSE.txt. +Add cast to vec_perm for SFMT-alti.c, SFMT-alti64.c. +combine source codes. + +ver 1.1 +------- +The period certification method is changed from constant to function. +The convert functions from 32-bit and 64-bit integer to double are added. +The documentation is changed. +Sample programs are added. + +ver 1.0 +------- +The first version. Index: src/random/SFMT-alti.h =================================================================== --- src/random/SFMT-alti.h (Revision 0) +++ src/random/SFMT-alti.h (Revision 0) @@ -0,0 +1,156 @@ +/** + * @file SFMT-alti.h + * + * @brief SIMD oriented Fast Mersenne Twister(SFMT) + * pseudorandom number generator + * + * @author Mutsuo Saito (Hiroshima University) + * @author Makoto Matsumoto (Hiroshima University) + * + * Copyright (C) 2007 Mutsuo Saito, Makoto Matsumoto and Hiroshima + * University. All rights reserved. + * + * The new BSD License is applied to this software. + * see LICENSE.txt + */ + +#ifndef SFMT_ALTI_H +#define SFMT_ALTI_H + +inline static vector unsigned int vec_recursion(vector unsigned int a, + vector unsigned int b, + vector unsigned int c, + vector unsigned int d) + ALWAYSINLINE; + +/** + * This function represents the recursion formula in AltiVec and BIG ENDIAN. + * @param a a 128-bit part of the interal state array + * @param b a 128-bit part of the interal state array + * @param c a 128-bit part of the interal state array + * @param d a 128-bit part of the interal state array + * @return output + */ +inline static vector unsigned int vec_recursion(vector unsigned int a, + vector unsigned int b, + vector unsigned int c, + vector unsigned int d) { + + const vector unsigned int sl1 = ALTI_SL1; + const vector unsigned int sr1 = ALTI_SR1; +#ifdef ONLY64 + const vector unsigned int mask = ALTI_MSK64; + const vector unsigned char perm_sl = ALTI_SL2_PERM64; + const vector unsigned char perm_sr = ALTI_SR2_PERM64; +#else + const vector unsigned int mask = ALTI_MSK; + const vector unsigned char perm_sl = ALTI_SL2_PERM; + const vector unsigned char perm_sr = ALTI_SR2_PERM; +#endif + vector unsigned int v, w, x, y, z; + x = vec_perm(a, (vector unsigned int)perm_sl, perm_sl); + v = a; + y = vec_sr(b, sr1); + z = vec_perm(c, (vector unsigned int)perm_sr, perm_sr); + w = vec_sl(d, sl1); + z = vec_xor(z, w); + y = vec_and(y, mask); + v = vec_xor(v, x); + z = vec_xor(z, y); + z = vec_xor(z, v); + return z; +} + +/** + * This function fills the internal state array with pseudorandom + * integers. + */ +inline static void gen_rand_all(void) { + int i; + vector unsigned int r, r1, r2; + + r1 = sfmt[N - 2].s; + r2 = sfmt[N - 1].s; + for (i = 0; i < N - POS1; i++) { + r = vec_recursion(sfmt[i].s, sfmt[i + POS1].s, r1, r2); + sfmt[i].s = r; + r1 = r2; + r2 = r; + } + for (; i < N; i++) { + r = vec_recursion(sfmt[i].s, sfmt[i + POS1 - N].s, r1, r2); + sfmt[i].s = r; + r1 = r2; + r2 = r; + } +} + +/** + * This function fills the user-specified array with pseudorandom + * integers. + * + * @param array an 128-bit array to be filled by pseudorandom numbers. + * @param size number of 128-bit pesudorandom numbers to be generated. + */ +inline static void gen_rand_array(w128_t *array, int size) { + int i, j; + vector unsigned int r, r1, r2; + + r1 = sfmt[N - 2].s; + r2 = sfmt[N - 1].s; + for (i = 0; i < N - POS1; i++) { + r = vec_recursion(sfmt[i].s, sfmt[i + POS1].s, r1, r2); + array[i].s = r; + r1 = r2; + r2 = r; + } + for (; i < N; i++) { + r = vec_recursion(sfmt[i].s, array[i + POS1 - N].s, r1, r2); + array[i].s = r; + r1 = r2; + r2 = r; + } + /* main loop */ + for (; i < size - N; i++) { + r = vec_recursion(array[i - N].s, array[i + POS1 - N].s, r1, r2); + array[i].s = r; + r1 = r2; + r2 = r; + } + for (j = 0; j < 2 * N - size; j++) { + sfmt[j].s = array[j + size - N].s; + } + for (; i < size; i++) { + r = vec_recursion(array[i - N].s, array[i + POS1 - N].s, r1, r2); + array[i].s = r; + sfmt[j++].s = r; + r1 = r2; + r2 = r; + } +} + +#ifndef ONLY64 +#if defined(__APPLE__) +#define ALTI_SWAP (vector unsigned char) \ + (4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 14, 15, 8, 9, 10, 11) +#else +#define ALTI_SWAP {4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 14, 15, 8, 9, 10, 11} +#endif +/** + * This function swaps high and low 32-bit of 64-bit integers in user + * specified array. + * + * @param array an 128-bit array to be swaped. + * @param size size of 128-bit array. + */ +inline static void swap(w128_t *array, int size) { + int i; + const vector unsigned char perm = ALTI_SWAP; + + for (i = 0; i < size; i++) { + array[i].s = vec_perm(array[i].s, (vector unsigned int)perm, perm); + } +} +#endif + +#endif Index: src/random/SFMT-params86243.h =================================================================== --- src/random/SFMT-params86243.h (Revision 0) +++ src/random/SFMT-params86243.h (Revision 0) @@ -0,0 +1,46 @@ +#ifndef SFMT_PARAMS86243_H +#define SFMT_PARAMS86243_H + +#define POS1 366 +#define SL1 6 +#define SL2 7 +#define SR1 19 +#define SR2 1 +#define MSK1 0xfdbffbffU +#define MSK2 0xbff7ff3fU +#define MSK3 0xfd77efffU +#define MSK4 0xbf9ff3ffU +#define PARITY1 0x00000001U +#define PARITY2 0x00000000U +#define PARITY3 0x00000000U +#define PARITY4 0xe9528d85U + + +/* PARAMETERS FOR ALTIVEC */ +#if defined(__APPLE__) /* For OSX */ + #define ALTI_SL1 (vector unsigned int)(SL1, SL1, SL1, SL1) + #define ALTI_SR1 (vector unsigned int)(SR1, SR1, SR1, SR1) + #define ALTI_MSK (vector unsigned int)(MSK1, MSK2, MSK3, MSK4) + #define ALTI_MSK64 \ + (vector unsigned int)(MSK2, MSK1, MSK4, MSK3) + #define ALTI_SL2_PERM \ + (vector unsigned char)(25,25,25,25,3,25,25,25,7,0,1,2,11,4,5,6) + #define ALTI_SL2_PERM64 \ + (vector unsigned char)(7,25,25,25,25,25,25,25,15,0,1,2,3,4,5,6) + #define ALTI_SR2_PERM \ + (vector unsigned char)(7,0,1,2,11,4,5,6,15,8,9,10,17,12,13,14) + #define ALTI_SR2_PERM64 \ + (vector unsigned char)(15,0,1,2,3,4,5,6,17,8,9,10,11,12,13,14) +#else /* For OTHER OSs(Linux?) */ + #define ALTI_SL1 {SL1, SL1, SL1, SL1} + #define ALTI_SR1 {SR1, SR1, SR1, SR1} + #define ALTI_MSK {MSK1, MSK2, MSK3, MSK4} + #define ALTI_MSK64 {MSK2, MSK1, MSK4, MSK3} + #define ALTI_SL2_PERM {25,25,25,25,3,25,25,25,7,0,1,2,11,4,5,6} + #define ALTI_SL2_PERM64 {7,25,25,25,25,25,25,25,15,0,1,2,3,4,5,6} + #define ALTI_SR2_PERM {7,0,1,2,11,4,5,6,15,8,9,10,17,12,13,14} + #define ALTI_SR2_PERM64 {15,0,1,2,3,4,5,6,17,8,9,10,11,12,13,14} +#endif /* For OSX */ +#define IDSTR "SFMT-86243:366-6-7-19-1:fdbffbff-bff7ff3f-fd77efff-bf9ff3ff" + +#endif /* SFMT_PARAMS86243_H */ Index: src/random/SFMT.c =================================================================== --- src/random/SFMT.c (Revision 0) +++ src/random/SFMT.c (Revision 0) @@ -0,0 +1,694 @@ +/** + * @file SFMT.c + * @brief SIMD oriented Fast Mersenne Twister(SFMT) + * + * @author Mutsuo Saito (Hiroshima University) + * @author Makoto Matsumoto (Hiroshima University) + * + * Copyright (C) 2006,2007 Mutsuo Saito, Makoto Matsumoto and Hiroshima + * University. All rights reserved. + * + * The new BSD License is applied to this software, see LICENSE.txt + */ +#include +#include +#include "SFMT.h" +#include "SFMT-params.h" + +#if defined(__BIG_ENDIAN__) && !defined(__amd64) && !defined(BIG_ENDIAN64) +#define BIG_ENDIAN64 1 +#endif +#if defined(HAVE_ALTIVEC) && !defined(BIG_ENDIAN64) +#define BIG_ENDIAN64 1 +#endif +#if defined(ONLY64) && !defined(BIG_ENDIAN64) + #if defined(__GNUC__) + #error "-DONLY64 must be specified with -DBIG_ENDIAN64" + #endif +#undef ONLY64 +#endif +/*------------------------------------------------------ + 128-bit SIMD data type for Altivec, SSE2 or standard C + ------------------------------------------------------*/ +#if defined(HAVE_ALTIVEC) + #if !defined(__APPLE__) + #include + #endif +/** 128-bit data structure */ +union W128_T { + vector unsigned int s; + uint32_t u[4]; +}; +/** 128-bit data type */ +typedef union W128_T w128_t; + +#elif defined(HAVE_SSE2) + #include + +/** 128-bit data structure */ +union W128_T { + __m128i si; + uint32_t u[4]; +}; +/** 128-bit data type */ +typedef union W128_T w128_t; + +#else + +/** 128-bit data structure */ +struct W128_T { + uint32_t u[4]; +}; +/** 128-bit data type */ +typedef struct W128_T w128_t; + +#endif + +/*-------------------------------------- + FILE GLOBAL VARIABLES + internal state, index counter and flag + --------------------------------------*/ +/** the 128-bit internal state array */ +static w128_t sfmt[N]; +/** the 32bit integer pointer to the 128-bit internal state array */ +static uint32_t *psfmt32 = &sfmt[0].u[0]; +#if !defined(BIG_ENDIAN64) || defined(ONLY64) +/** the 64bit integer pointer to the 128-bit internal state array */ +static uint64_t *psfmt64 = (uint64_t *)&sfmt[0].u[0]; +#endif +/** index counter to the 32-bit internal state array */ +static int idx; +/** a flag: it is 0 if and only if the internal state is not yet + * initialized. */ +static int initialized = 0; +/** a parity check vector which certificate the period of 2^{MEXP} */ +static uint32_t parity[4] = {PARITY1, PARITY2, PARITY3, PARITY4}; + +/*---------------- + STATIC FUNCTIONS + ----------------*/ +inline static int idxof(int i); +inline static void rshift128(w128_t *out, w128_t const *in, int shift); +inline static void lshift128(w128_t *out, w128_t const *in, int shift); +inline static void gen_rand_all(void); +inline static void gen_rand_array(w128_t *array, int size); +inline static uint32_t func1(uint32_t x); +inline static uint32_t func2(uint32_t x); +static void period_certification(void); +#if defined(BIG_ENDIAN64) && !defined(ONLY64) +inline static void swap(w128_t *array, int size); +#endif + +#if defined(HAVE_ALTIVEC) + #include "SFMT-alti.h" +#elif defined(HAVE_SSE2) + #include "SFMT-sse2.h" +#endif + +/** + * This function simulate a 64-bit index of LITTLE ENDIAN + * in BIG ENDIAN machine. + */ +#ifdef ONLY64 +inline static int idxof(int i) { + return i ^ 1; +} +#else +inline static int idxof(int i) { + return i; +} +#endif +/** + * This function simulates SIMD 128-bit right shift by the standard C. + * The 128-bit integer given in in is shifted by (shift * 8) bits. + * This function simulates the LITTLE ENDIAN SIMD. + * @param out the output of this function + * @param in the 128-bit data to be shifted + * @param shift the shift value + */ +#ifdef ONLY64 +inline static void rshift128(w128_t *out, w128_t const *in, int shift) { + uint64_t th, tl, oh, ol; + + th = ((uint64_t)in->u[2] << 32) | ((uint64_t)in->u[3]); + tl = ((uint64_t)in->u[0] << 32) | ((uint64_t)in->u[1]); + + oh = th >> (shift * 8); + ol = tl >> (shift * 8); + ol |= th << (64 - shift * 8); + out->u[0] = (uint32_t)(ol >> 32); + out->u[1] = (uint32_t)ol; + out->u[2] = (uint32_t)(oh >> 32); + out->u[3] = (uint32_t)oh; +} +#else +inline static void rshift128(w128_t *out, w128_t const *in, int shift) { + uint64_t th, tl, oh, ol; + + th = ((uint64_t)in->u[3] << 32) | ((uint64_t)in->u[2]); + tl = ((uint64_t)in->u[1] << 32) | ((uint64_t)in->u[0]); + + oh = th >> (shift * 8); + ol = tl >> (shift * 8); + ol |= th << (64 - shift * 8); + out->u[1] = (uint32_t)(ol >> 32); + out->u[0] = (uint32_t)ol; + out->u[3] = (uint32_t)(oh >> 32); + out->u[2] = (uint32_t)oh; +} +#endif +/** + * This function simulates SIMD 128-bit left shift by the standard C. + * The 128-bit integer given in in is shifted by (shift * 8) bits. + * This function simulates the LITTLE ENDIAN SIMD. + * @param out the output of this function + * @param in the 128-bit data to be shifted + * @param shift the shift value + */ +#ifdef ONLY64 +inline static void lshift128(w128_t *out, w128_t const *in, int shift) { + uint64_t th, tl, oh, ol; + + th = ((uint64_t)in->u[2] << 32) | ((uint64_t)in->u[3]); + tl = ((uint64_t)in->u[0] << 32) | ((uint64_t)in->u[1]); + + oh = th << (shift * 8); + ol = tl << (shift * 8); + oh |= tl >> (64 - shift * 8); + out->u[0] = (uint32_t)(ol >> 32); + out->u[1] = (uint32_t)ol; + out->u[2] = (uint32_t)(oh >> 32); + out->u[3] = (uint32_t)oh; +} +#else +inline static void lshift128(w128_t *out, w128_t const *in, int shift) { + uint64_t th, tl, oh, ol; + + th = ((uint64_t)in->u[3] << 32) | ((uint64_t)in->u[2]); + tl = ((uint64_t)in->u[1] << 32) | ((uint64_t)in->u[0]); + + oh = th << (shift * 8); + ol = tl << (shift * 8); + oh |= tl >> (64 - shift * 8); + out->u[1] = (uint32_t)(ol >> 32); + out->u[0] = (uint32_t)ol; + out->u[3] = (uint32_t)(oh >> 32); + out->u[2] = (uint32_t)oh; +} +#endif + +/** + * This function represents the recursion formula. + * @param r output + * @param a a 128-bit part of the internal state array + * @param b a 128-bit part of the internal state array + * @param c a 128-bit part of the internal state array + * @param d a 128-bit part of the internal state array + */ +#if (!defined(HAVE_ALTIVEC)) && (!defined(HAVE_SSE2)) +#ifdef ONLY64 +inline static void do_recursion(w128_t *r, w128_t *a, w128_t *b, w128_t *c, + w128_t *d) { + w128_t x; + w128_t y; + + lshift128(&x, a, SL2); + rshift128(&y, c, SR2); + r->u[0] = a->u[0] ^ x.u[0] ^ ((b->u[0] >> SR1) & MSK2) ^ y.u[0] + ^ (d->u[0] << SL1); + r->u[1] = a->u[1] ^ x.u[1] ^ ((b->u[1] >> SR1) & MSK1) ^ y.u[1] + ^ (d->u[1] << SL1); + r->u[2] = a->u[2] ^ x.u[2] ^ ((b->u[2] >> SR1) & MSK4) ^ y.u[2] + ^ (d->u[2] << SL1); + r->u[3] = a->u[3] ^ x.u[3] ^ ((b->u[3] >> SR1) & MSK3) ^ y.u[3] + ^ (d->u[3] << SL1); +} +#else +inline static void do_recursion(w128_t *r, w128_t *a, w128_t *b, w128_t *c, + w128_t *d) { + w128_t x; + w128_t y; + + lshift128(&x, a, SL2); + rshift128(&y, c, SR2); + r->u[0] = a->u[0] ^ x.u[0] ^ ((b->u[0] >> SR1) & MSK1) ^ y.u[0] + ^ (d->u[0] << SL1); + r->u[1] = a->u[1] ^ x.u[1] ^ ((b->u[1] >> SR1) & MSK2) ^ y.u[1] + ^ (d->u[1] << SL1); + r->u[2] = a->u[2] ^ x.u[2] ^ ((b->u[2] >> SR1) & MSK3) ^ y.u[2] + ^ (d->u[2] << SL1); + r->u[3] = a->u[3] ^ x.u[3] ^ ((b->u[3] >> SR1) & MSK4) ^ y.u[3] + ^ (d->u[3] << SL1); +} +#endif +#endif + +#if (!defined(HAVE_ALTIVEC)) && (!defined(HAVE_SSE2)) +/** + * This function fills the internal state array with pseudorandom + * integers. + */ +inline static void gen_rand_all(void) { + int i; + w128_t *r1, *r2; + + r1 = &sfmt[N - 2]; + r2 = &sfmt[N - 1]; + for (i = 0; i < N - POS1; i++) { + do_recursion(&sfmt[i], &sfmt[i], &sfmt[i + POS1], r1, r2); + r1 = r2; + r2 = &sfmt[i]; + } + for (; i < N; i++) { + do_recursion(&sfmt[i], &sfmt[i], &sfmt[i + POS1 - N], r1, r2); + r1 = r2; + r2 = &sfmt[i]; + } +} + +/** + * This function fills the user-specified array with pseudorandom + * integers. + * + * @param array an 128-bit array to be filled by pseudorandom numbers. + * @param size number of 128-bit pseudorandom numbers to be generated. + */ +inline static void gen_rand_array(w128_t *array, int size) { + int i, j; + w128_t *r1, *r2; + + r1 = &sfmt[N - 2]; + r2 = &sfmt[N - 1]; + for (i = 0; i < N - POS1; i++) { + do_recursion(&array[i], &sfmt[i], &sfmt[i + POS1], r1, r2); + r1 = r2; + r2 = &array[i]; + } + for (; i < N; i++) { + do_recursion(&array[i], &sfmt[i], &array[i + POS1 - N], r1, r2); + r1 = r2; + r2 = &array[i]; + } + for (; i < size - N; i++) { + do_recursion(&array[i], &array[i - N], &array[i + POS1 - N], r1, r2); + r1 = r2; + r2 = &array[i]; + } + for (j = 0; j < 2 * N - size; j++) { + sfmt[j] = array[j + size - N]; + } + for (; i < size; i++, j++) { + do_recursion(&array[i], &array[i - N], &array[i + POS1 - N], r1, r2); + r1 = r2; + r2 = &array[i]; + sfmt[j] = array[i]; + } +} +#endif + +#if defined(BIG_ENDIAN64) && !defined(ONLY64) && !defined(HAVE_ALTIVEC) +inline static void swap(w128_t *array, int size) { + int i; + uint32_t x, y; + + for (i = 0; i < size; i++) { + x = array[i].u[0]; + y = array[i].u[2]; + array[i].u[0] = array[i].u[1]; + array[i].u[2] = array[i].u[3]; + array[i].u[1] = x; + array[i].u[3] = y; + } +} +#endif +/** + * This function represents a function used in the initialization + * by init_by_array + * @param x 32-bit integer + * @return 32-bit integer + */ +static uint32_t func1(uint32_t x) { + return (x ^ (x >> 27)) * (uint32_t)1664525UL; +} + +/** + * This function represents a function used in the initialization + * by init_by_array + * @param x 32-bit integer + * @return 32-bit integer + */ +static uint32_t func2(uint32_t x) { + return (x ^ (x >> 27)) * (uint32_t)1566083941UL; +} + +/** + * This function certificate the period of 2^{MEXP} + */ +static void period_certification(void) { + int inner = 0; + int i, j; + uint32_t work; + + for (i = 0; i < 4; i++) + inner ^= psfmt32[idxof(i)] & parity[i]; + for (i = 16; i > 0; i >>= 1) + inner ^= inner >> i; + inner &= 1; + /* check OK */ + if (inner == 1) { + return; + } + /* check NG, and modification */ + for (i = 0; i < 4; i++) { + work = 1; + for (j = 0; j < 32; j++) { + if ((work & parity[i]) != 0) { + psfmt32[idxof(i)] ^= work; + return; + } + work = work << 1; + } + } +} + +/*---------------- + PUBLIC FUNCTIONS + ----------------*/ +/** + * This function returns the identification string. + * The string shows the word size, the Mersenne exponent, + * and all parameters of this generator. + */ +static INLINE const char *get_idstring(void) { + return IDSTR; +} + +/** + * This function returns the minimum size of array used for \b + * fill_array32() function. + * @return minimum size of array used for fill_array32() function. + */ +static INLINE int get_min_array_size32(void) { + return N32; +} + +/** + * This function returns the minimum size of array used for \b + * fill_array64() function. + * @return minimum size of array used for fill_array64() function. + */ +static INLINE int get_min_array_size64(void) { + return N64; +} + +#ifndef ONLY64 +/** + * This function generates and returns 32-bit pseudorandom number. + * init_gen_rand or init_by_array must be called before this function. + * @return 32-bit pseudorandom number + */ +static INLINE uint32_t gen_rand32(void) { + uint32_t r; + + assert(initialized); + if (idx >= N32) { + gen_rand_all(); + idx = 0; + } + r = psfmt32[idx++]; + return r; +} +#endif +/** + * This function generates and returns 64-bit pseudorandom number. + * init_gen_rand or init_by_array must be called before this function. + * The function gen_rand64 should not be called after gen_rand32, + * unless an initialization is again executed. + * @return 64-bit pseudorandom number + */ +static INLINE uint64_t gen_rand64(void) { +#if defined(BIG_ENDIAN64) && !defined(ONLY64) + uint32_t r1, r2; +#else + uint64_t r; +#endif + + assert(initialized); + assert(idx % 2 == 0); + + if (idx >= N32) { + gen_rand_all(); + idx = 0; + } +#if defined(BIG_ENDIAN64) && !defined(ONLY64) + r1 = psfmt32[idx]; + r2 = psfmt32[idx + 1]; + idx += 2; + return ((uint64_t)r2 << 32) | r1; +#else + r = psfmt64[idx / 2]; + idx += 2; + return r; +#endif +} + +#ifndef ONLY64 +/** + * This function generates pseudorandom 32-bit integers in the + * specified array[] by one call. The number of pseudorandom integers + * is specified by the argument size, which must be at least 624 and a + * multiple of four. The generation by this function is much faster + * than the following gen_rand function. + * + * For initialization, init_gen_rand or init_by_array must be called + * before the first call of this function. This function can not be + * used after calling gen_rand function, without initialization. + * + * @param array an array where pseudorandom 32-bit integers are filled + * by this function. The pointer to the array must be \b "aligned" + * (namely, must be a multiple of 16) in the SIMD version, since it + * refers to the address of a 128-bit integer. In the standard C + * version, the pointer is arbitrary. + * + * @param size the number of 32-bit pseudorandom integers to be + * generated. size must be a multiple of 4, and greater than or equal + * to (MEXP / 128 + 1) * 4. + * + * @note \b memalign or \b posix_memalign is available to get aligned + * memory. Mac OSX doesn't have these functions, but \b malloc of OSX + * returns the pointer to the aligned memory block. + */ +static INLINE void fill_array32(uint32_t *array, int size) { + assert(initialized); + assert(idx == N32); + assert(size % 4 == 0); + assert(size >= N32); + + gen_rand_array((w128_t *)array, size / 4); + idx = N32; +} +#endif + +/** + * This function generates pseudorandom 64-bit integers in the + * specified array[] by one call. The number of pseudorandom integers + * is specified by the argument size, which must be at least 312 and a + * multiple of two. The generation by this function is much faster + * than the following gen_rand function. + * + * For initialization, init_gen_rand or init_by_array must be called + * before the first call of this function. This function can not be + * used after calling gen_rand function, without initialization. + * + * @param array an array where pseudorandom 64-bit integers are filled + * by this function. The pointer to the array must be "aligned" + * (namely, must be a multiple of 16) in the SIMD version, since it + * refers to the address of a 128-bit integer. In the standard C + * version, the pointer is arbitrary. + * + * @param size the number of 64-bit pseudorandom integers to be + * generated. size must be a multiple of 2, and greater than or equal + * to (MEXP / 128 + 1) * 2 + * + * @note \b memalign or \b posix_memalign is available to get aligned + * memory. Mac OSX doesn't have these functions, but \b malloc of OSX + * returns the pointer to the aligned memory block. + */ +static INLINE void fill_array64(uint64_t *array, int size) { + assert(initialized); + assert(idx == N32); + assert(size % 2 == 0); + assert(size >= N64); + + gen_rand_array((w128_t *)array, size / 2); + idx = N32; + +#if defined(BIG_ENDIAN64) && !defined(ONLY64) + swap((w128_t *)array, size /2); +#endif +} + +/** + * This function initializes the internal state array with a 32-bit + * integer seed. + * + * @param seed a 32-bit integer used as the seed. + */ +static void init_gen_rand(uint32_t seed) { + int i; + + psfmt32[idxof(0)] = seed; + for (i = 1; i < N32; i++) { + psfmt32[idxof(i)] = 1812433253UL * (psfmt32[idxof(i - 1)] + ^ (psfmt32[idxof(i - 1)] >> 30)) + + i; + } + idx = N32; + period_certification(); + initialized = 1; +} + +/** + * This function initializes the internal state array, + * with an array of 32-bit integers used as the seeds + * @param init_key the array of 32-bit integers, used as a seed. + * @param key_length the length of init_key. + */ +static void init_by_array(uint32_t *init_key, int key_length) { + int i, j, count; + uint32_t r; + int lag; + int mid; + int size = N * 4; + + if (size >= 623) { + lag = 11; + } else if (size >= 68) { + lag = 7; + } else if (size >= 39) { + lag = 5; + } else { + lag = 3; + } + mid = (size - lag) / 2; + + memset(sfmt, 0x8b, sizeof(sfmt)); + if (key_length + 1 > N32) { + count = key_length + 1; + } else { + count = N32; + } + r = func1(psfmt32[idxof(0)] ^ psfmt32[idxof(mid)] + ^ psfmt32[idxof(N32 - 1)]); + psfmt32[idxof(mid)] += r; + r += key_length; + psfmt32[idxof(mid + lag)] += r; + psfmt32[idxof(0)] = r; + + count--; + for (i = 1, j = 0; (j < count) && (j < key_length); j++) { + r = func1(psfmt32[idxof(i)] ^ psfmt32[idxof((i + mid) % N32)] + ^ psfmt32[idxof((i + N32 - 1) % N32)]); + psfmt32[idxof((i + mid) % N32)] += r; + r += init_key[j] + i; + psfmt32[idxof((i + mid + lag) % N32)] += r; + psfmt32[idxof(i)] = r; + i = (i + 1) % N32; + } + for (; j < count; j++) { + r = func1(psfmt32[idxof(i)] ^ psfmt32[idxof((i + mid) % N32)] + ^ psfmt32[idxof((i + N32 - 1) % N32)]); + psfmt32[idxof((i + mid) % N32)] += r; + r += i; + psfmt32[idxof((i + mid + lag) % N32)] += r; + psfmt32[idxof(i)] = r; + i = (i + 1) % N32; + } + for (j = 0; j < N32; j++) { + r = func2(psfmt32[idxof(i)] + psfmt32[idxof((i + mid) % N32)] + + psfmt32[idxof((i + N32 - 1) % N32)]); + psfmt32[idxof((i + mid) % N32)] ^= r; + r -= i; + psfmt32[idxof((i + mid + lag) % N32)] ^= r; + psfmt32[idxof(i)] = r; + i = (i + 1) % N32; + } + + idx = N32; + period_certification(); + initialized = 1; +} + +/* These real versions are due to Isaku Wada */ +/** generates a random number on [0,1]-real-interval */ +inline static double to_real1(uint32_t v) +{ + return v * (1.0/4294967295.0); + /* divided by 2^32-1 */ +} + +/** generates a random number on [0,1]-real-interval */ +inline static double genrand_real1(void) +{ + return to_real1(gen_rand32()); +} + +/** generates a random number on [0,1)-real-interval */ +inline static double to_real2(uint32_t v) +{ + return v * (1.0/4294967296.0); + /* divided by 2^32 */ +} + +/** generates a random number on [0,1)-real-interval */ +inline static double genrand_real2(void) +{ + return to_real2(gen_rand32()); +} + +/** generates a random number on (0,1)-real-interval */ +inline static double to_real3(uint32_t v) +{ + return (((double)v) + 0.5)*(1.0/4294967296.0); + /* divided by 2^32 */ +} + +/** generates a random number on (0,1)-real-interval */ +inline static double genrand_real3(void) +{ + return to_real3(gen_rand32()); +} +/** These real versions are due to Isaku Wada */ + +/** generates a random number on [0,1) with 53-bit resolution*/ +inline static double to_res53(uint64_t v) +{ + return v * (1.0/18446744073709551616.0L); +} + +/** generates a random number on [0,1) with 53-bit resolution from two + * 32 bit integers */ +inline static double to_res53_mix(uint32_t x, uint32_t y) +{ + return to_res53(x | ((uint64_t)y << 32)); +} + +/** generates a random number on [0,1) with 53-bit resolution + */ +inline static double genrand_res53(void) +{ + return to_res53(gen_rand64()); +} + +/** generates a random number on [0,1) with 53-bit resolution + using 32bit integer. + */ +inline static double genrand_res53_mix(void) +{ + uint32_t x, y; + + x = gen_rand32(); + y = gen_rand32(); + return to_res53_mix(x, y); +} + Index: src/random/SFMT-params44497.h =================================================================== --- src/random/SFMT-params44497.h (Revision 0) +++ src/random/SFMT-params44497.h (Revision 0) @@ -0,0 +1,46 @@ +#ifndef SFMT_PARAMS44497_H +#define SFMT_PARAMS44497_H + +#define POS1 330 +#define SL1 5 +#define SL2 3 +#define SR1 9 +#define SR2 3 +#define MSK1 0xeffffffbU +#define MSK2 0xdfbebfffU +#define MSK3 0xbfbf7befU +#define MSK4 0x9ffd7bffU +#define PARITY1 0x00000001U +#define PARITY2 0x00000000U +#define PARITY3 0xa3ac4000U +#define PARITY4 0xecc1327aU + + +/* PARAMETERS FOR ALTIVEC */ +#if defined(__APPLE__) /* For OSX */ + #define ALTI_SL1 (vector unsigned int)(SL1, SL1, SL1, SL1) + #define ALTI_SR1 (vector unsigned int)(SR1, SR1, SR1, SR1) + #define ALTI_MSK (vector unsigned int)(MSK1, MSK2, MSK3, MSK4) + #define ALTI_MSK64 \ + (vector unsigned int)(MSK2, MSK1, MSK4, MSK3) + #define ALTI_SL2_PERM \ + (vector unsigned char)(3,21,21,21,7,0,1,2,11,4,5,6,15,8,9,10) + #define ALTI_SL2_PERM64 \ + (vector unsigned char)(3,4,5,6,7,29,29,29,11,12,13,14,15,0,1,2) + #define ALTI_SR2_PERM \ + (vector unsigned char)(5,6,7,0,9,10,11,4,13,14,15,8,19,19,19,12) + #define ALTI_SR2_PERM64 \ + (vector unsigned char)(13,14,15,0,1,2,3,4,19,19,19,8,9,10,11,12) +#else /* For OTHER OSs(Linux?) */ + #define ALTI_SL1 {SL1, SL1, SL1, SL1} + #define ALTI_SR1 {SR1, SR1, SR1, SR1} + #define ALTI_MSK {MSK1, MSK2, MSK3, MSK4} + #define ALTI_MSK64 {MSK2, MSK1, MSK4, MSK3} + #define ALTI_SL2_PERM {3,21,21,21,7,0,1,2,11,4,5,6,15,8,9,10} + #define ALTI_SL2_PERM64 {3,4,5,6,7,29,29,29,11,12,13,14,15,0,1,2} + #define ALTI_SR2_PERM {5,6,7,0,9,10,11,4,13,14,15,8,19,19,19,12} + #define ALTI_SR2_PERM64 {13,14,15,0,1,2,3,4,19,19,19,8,9,10,11,12} +#endif /* For OSX */ +#define IDSTR "SFMT-44497:330-5-3-9-3:effffffb-dfbebfff-bfbf7bef-9ffd7bff" + +#endif /* SFMT_PARAMS44497_H */ Index: src/random/SFMT-params19937.h =================================================================== --- src/random/SFMT-params19937.h (Revision 0) +++ src/random/SFMT-params19937.h (Revision 0) @@ -0,0 +1,46 @@ +#ifndef SFMT_PARAMS19937_H +#define SFMT_PARAMS19937_H + +#define POS1 122 +#define SL1 18 +#define SL2 1 +#define SR1 11 +#define SR2 1 +#define MSK1 0xdfffffefU +#define MSK2 0xddfecb7fU +#define MSK3 0xbffaffffU +#define MSK4 0xbffffff6U +#define PARITY1 0x00000001U +#define PARITY2 0x00000000U +#define PARITY3 0x00000000U +#define PARITY4 0x13c9e684U + + +/* PARAMETERS FOR ALTIVEC */ +#if defined(__APPLE__) /* For OSX */ + #define ALTI_SL1 (vector unsigned int)(SL1, SL1, SL1, SL1) + #define ALTI_SR1 (vector unsigned int)(SR1, SR1, SR1, SR1) + #define ALTI_MSK (vector unsigned int)(MSK1, MSK2, MSK3, MSK4) + #define ALTI_MSK64 \ + (vector unsigned int)(MSK2, MSK1, MSK4, MSK3) + #define ALTI_SL2_PERM \ + (vector unsigned char)(1,2,3,23,5,6,7,0,9,10,11,4,13,14,15,8) + #define ALTI_SL2_PERM64 \ + (vector unsigned char)(1,2,3,4,5,6,7,31,9,10,11,12,13,14,15,0) + #define ALTI_SR2_PERM \ + (vector unsigned char)(7,0,1,2,11,4,5,6,15,8,9,10,17,12,13,14) + #define ALTI_SR2_PERM64 \ + (vector unsigned char)(15,0,1,2,3,4,5,6,17,8,9,10,11,12,13,14) +#else /* For OTHER OSs(Linux?) */ + #define ALTI_SL1 {SL1, SL1, SL1, SL1} + #define ALTI_SR1 {SR1, SR1, SR1, SR1} + #define ALTI_MSK {MSK1, MSK2, MSK3, MSK4} + #define ALTI_MSK64 {MSK2, MSK1, MSK4, MSK3} + #define ALTI_SL2_PERM {1,2,3,23,5,6,7,0,9,10,11,4,13,14,15,8} + #define ALTI_SL2_PERM64 {1,2,3,4,5,6,7,31,9,10,11,12,13,14,15,0} + #define ALTI_SR2_PERM {7,0,1,2,11,4,5,6,15,8,9,10,17,12,13,14} + #define ALTI_SR2_PERM64 {15,0,1,2,3,4,5,6,17,8,9,10,11,12,13,14} +#endif /* For OSX */ +#define IDSTR "SFMT-19937:122-18-1-11-1:dfffffef-ddfecb7f-bffaffff-bffffff6" + +#endif /* SFMT_PARAMS19937_H */ Index: src/random/SFMT-params2281.h =================================================================== --- src/random/SFMT-params2281.h (Revision 0) +++ src/random/SFMT-params2281.h (Revision 0) @@ -0,0 +1,46 @@ +#ifndef SFMT_PARAMS2281_H +#define SFMT_PARAMS2281_H + +#define POS1 12 +#define SL1 19 +#define SL2 1 +#define SR1 5 +#define SR2 1 +#define MSK1 0xbff7ffbfU +#define MSK2 0xfdfffffeU +#define MSK3 0xf7ffef7fU +#define MSK4 0xf2f7cbbfU +#define PARITY1 0x00000001U +#define PARITY2 0x00000000U +#define PARITY3 0x00000000U +#define PARITY4 0x41dfa600U + + +/* PARAMETERS FOR ALTIVEC */ +#if defined(__APPLE__) /* For OSX */ + #define ALTI_SL1 (vector unsigned int)(SL1, SL1, SL1, SL1) + #define ALTI_SR1 (vector unsigned int)(SR1, SR1, SR1, SR1) + #define ALTI_MSK (vector unsigned int)(MSK1, MSK2, MSK3, MSK4) + #define ALTI_MSK64 \ + (vector unsigned int)(MSK2, MSK1, MSK4, MSK3) + #define ALTI_SL2_PERM \ + (vector unsigned char)(1,2,3,23,5,6,7,0,9,10,11,4,13,14,15,8) + #define ALTI_SL2_PERM64 \ + (vector unsigned char)(1,2,3,4,5,6,7,31,9,10,11,12,13,14,15,0) + #define ALTI_SR2_PERM \ + (vector unsigned char)(7,0,1,2,11,4,5,6,15,8,9,10,17,12,13,14) + #define ALTI_SR2_PERM64 \ + (vector unsigned char)(15,0,1,2,3,4,5,6,17,8,9,10,11,12,13,14) +#else /* For OTHER OSs(Linux?) */ + #define ALTI_SL1 {SL1, SL1, SL1, SL1} + #define ALTI_SR1 {SR1, SR1, SR1, SR1} + #define ALTI_MSK {MSK1, MSK2, MSK3, MSK4} + #define ALTI_MSK64 {MSK2, MSK1, MSK4, MSK3} + #define ALTI_SL2_PERM {1,2,3,23,5,6,7,0,9,10,11,4,13,14,15,8} + #define ALTI_SL2_PERM64 {1,2,3,4,5,6,7,31,9,10,11,12,13,14,15,0} + #define ALTI_SR2_PERM {7,0,1,2,11,4,5,6,15,8,9,10,17,12,13,14} + #define ALTI_SR2_PERM64 {15,0,1,2,3,4,5,6,17,8,9,10,11,12,13,14} +#endif /* For OSX */ +#define IDSTR "SFMT-2281:12-19-1-5-1:bff7ffbf-fdfffffe-f7ffef7f-f2f7cbbf" + +#endif /* SFMT_PARAMS2281_H */ Index: src/random/SFMT-params4253.h =================================================================== --- src/random/SFMT-params4253.h (Revision 0) +++ src/random/SFMT-params4253.h (Revision 0) @@ -0,0 +1,46 @@ +#ifndef SFMT_PARAMS4253_H +#define SFMT_PARAMS4253_H + +#define POS1 17 +#define SL1 20 +#define SL2 1 +#define SR1 7 +#define SR2 1 +#define MSK1 0x9f7bffffU +#define MSK2 0x9fffff5fU +#define MSK3 0x3efffffbU +#define MSK4 0xfffff7bbU +#define PARITY1 0xa8000001U +#define PARITY2 0xaf5390a3U +#define PARITY3 0xb740b3f8U +#define PARITY4 0x6c11486dU + + +/* PARAMETERS FOR ALTIVEC */ +#if defined(__APPLE__) /* For OSX */ + #define ALTI_SL1 (vector unsigned int)(SL1, SL1, SL1, SL1) + #define ALTI_SR1 (vector unsigned int)(SR1, SR1, SR1, SR1) + #define ALTI_MSK (vector unsigned int)(MSK1, MSK2, MSK3, MSK4) + #define ALTI_MSK64 \ + (vector unsigned int)(MSK2, MSK1, MSK4, MSK3) + #define ALTI_SL2_PERM \ + (vector unsigned char)(1,2,3,23,5,6,7,0,9,10,11,4,13,14,15,8) + #define ALTI_SL2_PERM64 \ + (vector unsigned char)(1,2,3,4,5,6,7,31,9,10,11,12,13,14,15,0) + #define ALTI_SR2_PERM \ + (vector unsigned char)(7,0,1,2,11,4,5,6,15,8,9,10,17,12,13,14) + #define ALTI_SR2_PERM64 \ + (vector unsigned char)(15,0,1,2,3,4,5,6,17,8,9,10,11,12,13,14) +#else /* For OTHER OSs(Linux?) */ + #define ALTI_SL1 {SL1, SL1, SL1, SL1} + #define ALTI_SR1 {SR1, SR1, SR1, SR1} + #define ALTI_MSK {MSK1, MSK2, MSK3, MSK4} + #define ALTI_MSK64 {MSK2, MSK1, MSK4, MSK3} + #define ALTI_SL2_PERM {1,2,3,23,5,6,7,0,9,10,11,4,13,14,15,8} + #define ALTI_SL2_PERM64 {1,2,3,4,5,6,7,31,9,10,11,12,13,14,15,0} + #define ALTI_SR2_PERM {7,0,1,2,11,4,5,6,15,8,9,10,17,12,13,14} + #define ALTI_SR2_PERM64 {15,0,1,2,3,4,5,6,17,8,9,10,11,12,13,14} +#endif /* For OSX */ +#define IDSTR "SFMT-4253:17-20-1-7-1:9f7bffff-9fffff5f-3efffffb-fffff7bb" + +#endif /* SFMT_PARAMS4253_H */ Index: src/random/SFMT.h =================================================================== --- src/random/SFMT.h (Revision 0) +++ src/random/SFMT.h (Revision 0) @@ -0,0 +1,87 @@ +/** + * @file SFMT.h + * + * @brief SIMD oriented Fast Mersenne Twister(SFMT) pseudorandom + * number generator + * + * @author Mutsuo Saito (Hiroshima University) + * @author Makoto Matsumoto (Hiroshima University) + * + * Copyright (C) 2006, 2007 Mutsuo Saito, Makoto Matsumoto and Hiroshima + * University. All rights reserved. + * + * The new BSD License is applied to this software. + * see LICENSE.txt + * + * @note We assume that your system has inttypes.h. If your system + * doesn't have inttypes.h, you have to typedef uint32_t and uint64_t, + * and you have to define PRIu64 and PRIx64 in this file as follows: + * @verbatim + typedef unsigned int uint32_t + typedef unsigned long long uint64_t + #define PRIu64 "llu" + #define PRIx64 "llx" +@endverbatim + * uint32_t must be exactly 32-bit unsigned integer type (no more, no + * less), and uint64_t must be exactly 64-bit unsigned integer type. + * PRIu64 and PRIx64 are used for printf function to print 64-bit + * unsigned int and 64-bit unsigned int in hexadecimal format. + */ + +#ifndef SFMT_H +#define SFMT_H + +#include + +#if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) + #include +#elif defined(_MSC_VER) || defined(__BORLANDC__) + typedef unsigned int uint32_t; + typedef unsigned __int64 uint64_t; + #define inline __inline +#else + #include + #if defined(__GNUC__) + #define inline __inline__ + #endif +#endif + +#ifndef PRIu64 + #if defined(_MSC_VER) || defined(__BORLANDC__) + #define PRIu64 "I64u" + #define PRIx64 "I64x" + #else + #define PRIu64 "llu" + #define PRIx64 "llx" + #endif +#endif + +#if defined(__GNUC__) +#define ALWAYSINLINE __attribute__((always_inline)) +#else +#define ALWAYSINLINE +#endif + +#if defined(_MSC_VER) + #if _MSC_VER >= 1200 + #define PRE_ALWAYS __forceinline + #else + #define PRE_ALWAYS inline + #endif +#else + #define PRE_ALWAYS inline +#endif + +/* these are not needed in public +uint32_t gen_rand32(void); +uint64_t gen_rand64(void); +void fill_array32(uint32_t *array, int size); +void fill_array64(uint64_t *array, int size); +void init_gen_rand(uint32_t seed); +void init_by_array(uint32_t *init_key, int key_length); +const char *get_idstring(void); +int get_min_array_size32(void); +int get_min_array_size64(void); +*/ + +#endif Index: src/random/LICENSE.txt =================================================================== --- src/random/LICENSE.txt (Revision 0) +++ src/random/LICENSE.txt (Revision 0) @@ -0,0 +1,32 @@ +This License covers the the files in this subdirectory of the LDMud +source (src/random/). + +Copyright (c) 2006,2007 Mutsuo Saito, Makoto Matsumoto and Hiroshima +University. All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + copyright notice, this list of conditions and the following + disclaimer in the documentation and/or other materials provided + with the distribution. + * Neither the name of the Hiroshima University nor the names of + its contributors may be used to endorse or promote products + derived from this software without specific prior written + permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. Index: src/random/README.LDMUD =================================================================== --- src/random/README.LDMUD (Revision 0) +++ src/random/README.LDMUD (Revision 0) @@ -0,0 +1,8 @@ +This is SFMT-1.3.3, stripped down to what is required by the LDMud gamedriver. + +Additionally the 'public' function were made static as well because they are +probably not used without the wrapper. Therefore, their declarations have beed +moved from SFMT.h to SFMT.c. + +The files README.txt and LICENSE.txt tell you where to get the complete package. + Index: src/random/SFMT-params132049.h =================================================================== --- src/random/SFMT-params132049.h (Revision 0) +++ src/random/SFMT-params132049.h (Revision 0) @@ -0,0 +1,46 @@ +#ifndef SFMT_PARAMS132049_H +#define SFMT_PARAMS132049_H + +#define POS1 110 +#define SL1 19 +#define SL2 1 +#define SR1 21 +#define SR2 1 +#define MSK1 0xffffbb5fU +#define MSK2 0xfb6ebf95U +#define MSK3 0xfffefffaU +#define MSK4 0xcff77fffU +#define PARITY1 0x00000001U +#define PARITY2 0x00000000U +#define PARITY3 0xcb520000U +#define PARITY4 0xc7e91c7dU + + +/* PARAMETERS FOR ALTIVEC */ +#if defined(__APPLE__) /* For OSX */ + #define ALTI_SL1 (vector unsigned int)(SL1, SL1, SL1, SL1) + #define ALTI_SR1 (vector unsigned int)(SR1, SR1, SR1, SR1) + #define ALTI_MSK (vector unsigned int)(MSK1, MSK2, MSK3, MSK4) + #define ALTI_MSK64 \ + (vector unsigned int)(MSK2, MSK1, MSK4, MSK3) + #define ALTI_SL2_PERM \ + (vector unsigned char)(1,2,3,23,5,6,7,0,9,10,11,4,13,14,15,8) + #define ALTI_SL2_PERM64 \ + (vector unsigned char)(1,2,3,4,5,6,7,31,9,10,11,12,13,14,15,0) + #define ALTI_SR2_PERM \ + (vector unsigned char)(7,0,1,2,11,4,5,6,15,8,9,10,17,12,13,14) + #define ALTI_SR2_PERM64 \ + (vector unsigned char)(15,0,1,2,3,4,5,6,17,8,9,10,11,12,13,14) +#else /* For OTHER OSs(Linux?) */ + #define ALTI_SL1 {SL1, SL1, SL1, SL1} + #define ALTI_SR1 {SR1, SR1, SR1, SR1} + #define ALTI_MSK {MSK1, MSK2, MSK3, MSK4} + #define ALTI_MSK64 {MSK2, MSK1, MSK4, MSK3} + #define ALTI_SL2_PERM {1,2,3,23,5,6,7,0,9,10,11,4,13,14,15,8} + #define ALTI_SL2_PERM64 {1,2,3,4,5,6,7,31,9,10,11,12,13,14,15,0} + #define ALTI_SR2_PERM {7,0,1,2,11,4,5,6,15,8,9,10,17,12,13,14} + #define ALTI_SR2_PERM64 {15,0,1,2,3,4,5,6,17,8,9,10,11,12,13,14} +#endif /* For OSX */ +#define IDSTR "SFMT-132049:110-19-1-21-1:ffffbb5f-fb6ebf95-fffefffa-cff77fff" + +#endif /* SFMT_PARAMS132049_H */ Index: src/random/SFMT-params216091.h =================================================================== --- src/random/SFMT-params216091.h (Revision 0) +++ src/random/SFMT-params216091.h (Revision 0) @@ -0,0 +1,46 @@ +#ifndef SFMT_PARAMS216091_H +#define SFMT_PARAMS216091_H + +#define POS1 627 +#define SL1 11 +#define SL2 3 +#define SR1 10 +#define SR2 1 +#define MSK1 0xbff7bff7U +#define MSK2 0xbfffffffU +#define MSK3 0xbffffa7fU +#define MSK4 0xffddfbfbU +#define PARITY1 0xf8000001U +#define PARITY2 0x89e80709U +#define PARITY3 0x3bd2b64bU +#define PARITY4 0x0c64b1e4U + + +/* PARAMETERS FOR ALTIVEC */ +#if defined(__APPLE__) /* For OSX */ + #define ALTI_SL1 (vector unsigned int)(SL1, SL1, SL1, SL1) + #define ALTI_SR1 (vector unsigned int)(SR1, SR1, SR1, SR1) + #define ALTI_MSK (vector unsigned int)(MSK1, MSK2, MSK3, MSK4) + #define ALTI_MSK64 \ + (vector unsigned int)(MSK2, MSK1, MSK4, MSK3) + #define ALTI_SL2_PERM \ + (vector unsigned char)(3,21,21,21,7,0,1,2,11,4,5,6,15,8,9,10) + #define ALTI_SL2_PERM64 \ + (vector unsigned char)(3,4,5,6,7,29,29,29,11,12,13,14,15,0,1,2) + #define ALTI_SR2_PERM \ + (vector unsigned char)(7,0,1,2,11,4,5,6,15,8,9,10,17,12,13,14) + #define ALTI_SR2_PERM64 \ + (vector unsigned char)(15,0,1,2,3,4,5,6,17,8,9,10,11,12,13,14) +#else /* For OTHER OSs(Linux?) */ + #define ALTI_SL1 {SL1, SL1, SL1, SL1} + #define ALTI_SR1 {SR1, SR1, SR1, SR1} + #define ALTI_MSK {MSK1, MSK2, MSK3, MSK4} + #define ALTI_MSK64 {MSK2, MSK1, MSK4, MSK3} + #define ALTI_SL2_PERM {3,21,21,21,7,0,1,2,11,4,5,6,15,8,9,10} + #define ALTI_SL2_PERM64 {3,4,5,6,7,29,29,29,11,12,13,14,15,0,1,2} + #define ALTI_SR2_PERM {7,0,1,2,11,4,5,6,15,8,9,10,17,12,13,14} + #define ALTI_SR2_PERM64 {15,0,1,2,3,4,5,6,17,8,9,10,11,12,13,14} +#endif /* For OSX */ +#define IDSTR "SFMT-216091:627-11-3-10-1:bff7bff7-bfffffff-bffffa7f-ffddfbfb" + +#endif /* SFMT_PARAMS216091_H */ Index: src/random/SFMT-params1279.h =================================================================== --- src/random/SFMT-params1279.h (Revision 0) +++ src/random/SFMT-params1279.h (Revision 0) @@ -0,0 +1,46 @@ +#ifndef SFMT_PARAMS1279_H +#define SFMT_PARAMS1279_H + +#define POS1 7 +#define SL1 14 +#define SL2 3 +#define SR1 5 +#define SR2 1 +#define MSK1 0xf7fefffdU +#define MSK2 0x7fefcfffU +#define MSK3 0xaff3ef3fU +#define MSK4 0xb5ffff7fU +#define PARITY1 0x00000001U +#define PARITY2 0x00000000U +#define PARITY3 0x00000000U +#define PARITY4 0x20000000U + + +/* PARAMETERS FOR ALTIVEC */ +#if defined(__APPLE__) /* For OSX */ + #define ALTI_SL1 (vector unsigned int)(SL1, SL1, SL1, SL1) + #define ALTI_SR1 (vector unsigned int)(SR1, SR1, SR1, SR1) + #define ALTI_MSK (vector unsigned int)(MSK1, MSK2, MSK3, MSK4) + #define ALTI_MSK64 \ + (vector unsigned int)(MSK2, MSK1, MSK4, MSK3) + #define ALTI_SL2_PERM \ + (vector unsigned char)(3,21,21,21,7,0,1,2,11,4,5,6,15,8,9,10) + #define ALTI_SL2_PERM64 \ + (vector unsigned char)(3,4,5,6,7,29,29,29,11,12,13,14,15,0,1,2) + #define ALTI_SR2_PERM \ + (vector unsigned char)(7,0,1,2,11,4,5,6,15,8,9,10,17,12,13,14) + #define ALTI_SR2_PERM64 \ + (vector unsigned char)(15,0,1,2,3,4,5,6,17,8,9,10,11,12,13,14) +#else /* For OTHER OSs(Linux?) */ + #define ALTI_SL1 {SL1, SL1, SL1, SL1} + #define ALTI_SR1 {SR1, SR1, SR1, SR1} + #define ALTI_MSK {MSK1, MSK2, MSK3, MSK4} + #define ALTI_MSK64 {MSK2, MSK1, MSK4, MSK3} + #define ALTI_SL2_PERM {3,21,21,21,7,0,1,2,11,4,5,6,15,8,9,10} + #define ALTI_SL2_PERM64 {3,4,5,6,7,29,29,29,11,12,13,14,15,0,1,2} + #define ALTI_SR2_PERM {7,0,1,2,11,4,5,6,15,8,9,10,17,12,13,14} + #define ALTI_SR2_PERM64 {15,0,1,2,3,4,5,6,17,8,9,10,11,12,13,14} +#endif /* For OSX */ +#define IDSTR "SFMT-1279:7-14-3-5-1:f7fefffd-7fefcfff-aff3ef3f-b5ffff7f" + +#endif /* SFMT_PARAMS1279_H */ Index: src/random/SFMT-params11213.h =================================================================== --- src/random/SFMT-params11213.h (Revision 0) +++ src/random/SFMT-params11213.h (Revision 0) @@ -0,0 +1,46 @@ +#ifndef SFMT_PARAMS11213_H +#define SFMT_PARAMS11213_H + +#define POS1 68 +#define SL1 14 +#define SL2 3 +#define SR1 7 +#define SR2 3 +#define MSK1 0xeffff7fbU +#define MSK2 0xffffffefU +#define MSK3 0xdfdfbfffU +#define MSK4 0x7fffdbfdU +#define PARITY1 0x00000001U +#define PARITY2 0x00000000U +#define PARITY3 0xe8148000U +#define PARITY4 0xd0c7afa3U + + +/* PARAMETERS FOR ALTIVEC */ +#if defined(__APPLE__) /* For OSX */ + #define ALTI_SL1 (vector unsigned int)(SL1, SL1, SL1, SL1) + #define ALTI_SR1 (vector unsigned int)(SR1, SR1, SR1, SR1) + #define ALTI_MSK (vector unsigned int)(MSK1, MSK2, MSK3, MSK4) + #define ALTI_MSK64 \ + (vector unsigned int)(MSK2, MSK1, MSK4, MSK3) + #define ALTI_SL2_PERM \ + (vector unsigned char)(3,21,21,21,7,0,1,2,11,4,5,6,15,8,9,10) + #define ALTI_SL2_PERM64 \ + (vector unsigned char)(3,4,5,6,7,29,29,29,11,12,13,14,15,0,1,2) + #define ALTI_SR2_PERM \ + (vector unsigned char)(5,6,7,0,9,10,11,4,13,14,15,8,19,19,19,12) + #define ALTI_SR2_PERM64 \ + (vector unsigned char)(13,14,15,0,1,2,3,4,19,19,19,8,9,10,11,12) +#else /* For OTHER OSs(Linux?) */ + #define ALTI_SL1 {SL1, SL1, SL1, SL1} + #define ALTI_SR1 {SR1, SR1, SR1, SR1} + #define ALTI_MSK {MSK1, MSK2, MSK3, MSK4} + #define ALTI_MSK64 {MSK2, MSK1, MSK4, MSK3} + #define ALTI_SL2_PERM {3,21,21,21,7,0,1,2,11,4,5,6,15,8,9,10} + #define ALTI_SL2_PERM64 {3,4,5,6,7,29,29,29,11,12,13,14,15,0,1,2} + #define ALTI_SR2_PERM {5,6,7,0,9,10,11,4,13,14,15,8,19,19,19,12} + #define ALTI_SR2_PERM64 {13,14,15,0,1,2,3,4,19,19,19,8,9,10,11,12} +#endif /* For OSX */ +#define IDSTR "SFMT-11213:68-14-3-7-3:effff7fb-ffffffef-dfdfbfff-7fffdbfd" + +#endif /* SFMT_PARAMS11213_H */ Index: src/random/SFMT-sse2.h =================================================================== --- src/random/SFMT-sse2.h (Revision 0) +++ src/random/SFMT-sse2.h (Revision 0) @@ -0,0 +1,121 @@ +/** + * @file SFMT-sse2.h + * @brief SIMD oriented Fast Mersenne Twister(SFMT) for Intel SSE2 + * + * @author Mutsuo Saito (Hiroshima University) + * @author Makoto Matsumoto (Hiroshima University) + * + * @note We assume LITTLE ENDIAN in this file + * + * Copyright (C) 2006, 2007 Mutsuo Saito, Makoto Matsumoto and Hiroshima + * University. All rights reserved. + * + * The new BSD License is applied to this software, see LICENSE.txt + */ + +#ifndef SFMT_SSE2_H +#define SFMT_SSE2_H + +PRE_ALWAYS static __m128i mm_recursion(__m128i *a, __m128i *b, __m128i c, + __m128i d, __m128i mask) ALWAYSINLINE; + +/** + * This function represents the recursion formula. + * @param a a 128-bit part of the interal state array + * @param b a 128-bit part of the interal state array + * @param c a 128-bit part of the interal state array + * @param d a 128-bit part of the interal state array + * @param mask 128-bit mask + * @return output + */ +PRE_ALWAYS static __m128i mm_recursion(__m128i *a, __m128i *b, + __m128i c, __m128i d, __m128i mask) { + __m128i v, x, y, z; + + x = _mm_load_si128(a); + y = _mm_srli_epi32(*b, SR1); + z = _mm_srli_si128(c, SR2); + v = _mm_slli_epi32(d, SL1); + z = _mm_xor_si128(z, x); + z = _mm_xor_si128(z, v); + x = _mm_slli_si128(x, SL2); + y = _mm_and_si128(y, mask); + z = _mm_xor_si128(z, x); + z = _mm_xor_si128(z, y); + return z; +} + +/** + * This function fills the internal state array with pseudorandom + * integers. + */ +inline static void gen_rand_all(void) { + int i; + __m128i r, r1, r2, mask; + mask = _mm_set_epi32(MSK4, MSK3, MSK2, MSK1); + + r1 = _mm_load_si128(&sfmt[N - 2].si); + r2 = _mm_load_si128(&sfmt[N - 1].si); + for (i = 0; i < N - POS1; i++) { + r = mm_recursion(&sfmt[i].si, &sfmt[i + POS1].si, r1, r2, mask); + _mm_store_si128(&sfmt[i].si, r); + r1 = r2; + r2 = r; + } + for (; i < N; i++) { + r = mm_recursion(&sfmt[i].si, &sfmt[i + POS1 - N].si, r1, r2, mask); + _mm_store_si128(&sfmt[i].si, r); + r1 = r2; + r2 = r; + } +} + +/** + * This function fills the user-specified array with pseudorandom + * integers. + * + * @param array an 128-bit array to be filled by pseudorandom numbers. + * @param size number of 128-bit pesudorandom numbers to be generated. + */ +inline static void gen_rand_array(w128_t *array, int size) { + int i, j; + __m128i r, r1, r2, mask; + mask = _mm_set_epi32(MSK4, MSK3, MSK2, MSK1); + + r1 = _mm_load_si128(&sfmt[N - 2].si); + r2 = _mm_load_si128(&sfmt[N - 1].si); + for (i = 0; i < N - POS1; i++) { + r = mm_recursion(&sfmt[i].si, &sfmt[i + POS1].si, r1, r2, mask); + _mm_store_si128(&array[i].si, r); + r1 = r2; + r2 = r; + } + for (; i < N; i++) { + r = mm_recursion(&sfmt[i].si, &array[i + POS1 - N].si, r1, r2, mask); + _mm_store_si128(&array[i].si, r); + r1 = r2; + r2 = r; + } + /* main loop */ + for (; i < size - N; i++) { + r = mm_recursion(&array[i - N].si, &array[i + POS1 - N].si, r1, r2, + mask); + _mm_store_si128(&array[i].si, r); + r1 = r2; + r2 = r; + } + for (j = 0; j < 2 * N - size; j++) { + r = _mm_load_si128(&array[j + size - N].si); + _mm_store_si128(&sfmt[j].si, r); + } + for (; i < size; i++) { + r = mm_recursion(&array[i - N].si, &array[i + POS1 - N].si, r1, r2, + mask); + _mm_store_si128(&array[i].si, r); + _mm_store_si128(&sfmt[j++].si, r); + r1 = r2; + r2 = r; + } +} + +#endif Index: src/random/README.txt =================================================================== --- src/random/README.txt (Revision 0) +++ src/random/README.txt (Revision 0) @@ -0,0 +1,22 @@ + ================================================================= + SFMT ver. 1.3.3 + SIMD oriented Fast Mersenne Twister(SFMT) + + Mutsuo Saito (Hiroshima University) and + Makoto Matsumoto (Hiroshima University) + + Copyright (C) 2006, 2007 Mutsuo Saito, Makoto Matsumoto and Hiroshima + University. All rights reserved. + + The (modified) BSD License is applied to this software, see LICENSE.txt + ================================================================= + + To see documents, see html/index.html. + + To make test program, see html/howto-compile.html + + If you want to redistribute and/or change source files, see LICENSE.txt. + + When you change these files and redistribute them, PLEASE write your + e-mail address in redistribution and write to contact YOU first if + users of your changed source encounter troubles. Index: src/random/SFMT-params607.h =================================================================== --- src/random/SFMT-params607.h (Revision 0) +++ src/random/SFMT-params607.h (Revision 0) @@ -0,0 +1,46 @@ +#ifndef SFMT_PARAMS607_H +#define SFMT_PARAMS607_H + +#define POS1 2 +#define SL1 15 +#define SL2 3 +#define SR1 13 +#define SR2 3 +#define MSK1 0xfdff37ffU +#define MSK2 0xef7f3f7dU +#define MSK3 0xff777b7dU +#define MSK4 0x7ff7fb2fU +#define PARITY1 0x00000001U +#define PARITY2 0x00000000U +#define PARITY3 0x00000000U +#define PARITY4 0x5986f054U + + +/* PARAMETERS FOR ALTIVEC */ +#if defined(__APPLE__) /* For OSX */ + #define ALTI_SL1 (vector unsigned int)(SL1, SL1, SL1, SL1) + #define ALTI_SR1 (vector unsigned int)(SR1, SR1, SR1, SR1) + #define ALTI_MSK (vector unsigned int)(MSK1, MSK2, MSK3, MSK4) + #define ALTI_MSK64 \ + (vector unsigned int)(MSK2, MSK1, MSK4, MSK3) + #define ALTI_SL2_PERM \ + (vector unsigned char)(3,21,21,21,7,0,1,2,11,4,5,6,15,8,9,10) + #define ALTI_SL2_PERM64 \ + (vector unsigned char)(3,4,5,6,7,29,29,29,11,12,13,14,15,0,1,2) + #define ALTI_SR2_PERM \ + (vector unsigned char)(5,6,7,0,9,10,11,4,13,14,15,8,19,19,19,12) + #define ALTI_SR2_PERM64 \ + (vector unsigned char)(13,14,15,0,1,2,3,4,19,19,19,8,9,10,11,12) +#else /* For OTHER OSs(Linux?) */ + #define ALTI_SL1 {SL1, SL1, SL1, SL1} + #define ALTI_SR1 {SR1, SR1, SR1, SR1} + #define ALTI_MSK {MSK1, MSK2, MSK3, MSK4} + #define ALTI_MSK64 {MSK2, MSK1, MSK4, MSK3} + #define ALTI_SL2_PERM {3,21,21,21,7,0,1,2,11,4,5,6,15,8,9,10} + #define ALTI_SL2_PERM64 {3,4,5,6,7,29,29,29,11,12,13,14,15,0,1,2} + #define ALTI_SR2_PERM {5,6,7,0,9,10,11,4,13,14,15,8,19,19,19,12} + #define ALTI_SR2_PERM64 {13,14,15,0,1,2,3,4,19,19,19,8,9,10,11,12} +#endif /* For OSX */ +#define IDSTR "SFMT-607:2-15-3-13-3:fdff37ff-ef7f3f7d-ff777b7d-7ff7fb2f" + +#endif /* SFMT_PARAMS607_H */ Index: src/autoconf/configure.in =================================================================== --- src/autoconf/configure.in (Revision 2461) +++ src/autoconf/configure.in (Arbeitskopie) @@ -222,6 +222,7 @@ AC_MY_ARG_WITH(pcre-recursion-limit,3000,,[maximum number of recursions in PCRE package]) AC_MY_ARG_WITH(wizlist-file,WIZLIST,,[name of the wizlist file]) AC_MY_ARG_WITH(max_net_connects,10,,[maximum number of concurrent connection attempts]) +AC_MY_ARG_WITH(random-period-length,19937,[607 / 1279 / 2281 / 4253 / 11213 / 19937 / 44497 / 86243 / 132049 / 216091],[period length of the random number generator]) AC_ARG_WITH(setting,[ --with-setting=SETTING include a predefined setting],[ if test -f "settings/$withval" ; then @@ -465,6 +466,7 @@ AC_INT_VAL_FROM_WITH(total_trace_length) AC_INT_VAL_FROM_WITH(pcre_recursion_limit) AC_INT_VAL_FROM_WITH(max_net_connects) +AC_INT_VAL_FROM_WITH(random_period_length) if test "x$cdef_access_control" = "x#undef"; then cdef_access_log="#undef" @@ -2823,6 +2825,7 @@ AC_SUBST(val_wizlist_file) AC_SUBST(val_pcre_recursion_limit) AC_SUBST(val_max_net_connects) +AC_SUBST(val_random_period_length) dnl finally: some remaining stuff dnl Index: src/random.c =================================================================== --- src/random.c (Revision 2461) +++ src/random.c (Arbeitskopie) @@ -1,274 +1,109 @@ -/*--------------------------------------------------------------------------- - * Gamedriver: Random Generator 'Mersenne Twister' +/*------------------------------------------------------------------ + * Wrapper for the 'SIMD oriented Fast Mersenne Twister. * - * A C-program for MT19937, with initialization improved 2002/2/10. - * Coded by Takuji Nishimura and Makoto Matsumoto. - * This is a faster version by taking Shawn Cokus's optimization, - * Matthe Bellew's simplification, Isaku Wada's real version. - * - * Before using, initialize the state by using init_genrand(seed) - * or init_by_array(init_key, key_length). - * - * Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura, - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * 3. The names of its contributors may not be used to endorse or promote - * products derived from this software without specific prior written - * permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR - * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, - * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, - * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR - * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF - * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING - * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS - * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * - * Any feedback is very welcome. - * http://www.math.keio.ac.jp/matumoto/emt.html - * email: matumoto@math.keio.ac.jp - *--------------------------------------------------------------------------- + * SFMT was developed by Mutsuo Saito and Makoto Matsumoto, + * Hiroshima University, + * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html) + * SFMT was integrated to LDMud by Zesstra@MorgenGrauen (http://mg.mud.de) + *------------------------------------------------------------------ */ #include "driver.h" #include "random.h" +#include "backend.h" -/* Period parameters */ -#define N 624 -#define M 397 -#define MATRIX_A 0x9908b0dfUL /* constant vector a */ -#define UMASK 0x80000000UL /* most significant w-r bits */ -#define LMASK 0x7fffffffUL /* least significant r bits */ -#define MIXBITS(u,v) ( ((u) & UMASK) | ((v) & LMASK) ) -#define TWIST(u,v) ((MIXBITS(u,v) >> 1) ^ ((v)&1UL ? MATRIX_A : 0UL)) +/* This is included on purpose so that the compiler may inline some functions. + * They are anyway never used anywhere else, all other parts of the driver use + * only the wrapper functions in this file. + */ +#include "random/SFMT.c" -static unsigned long state[N]; /* the array for the state vector */ -static int left = 1; -static int initf = 0; -static unsigned long *next; +const unsigned int INIT_ARRAY_SIZE = 156U; // 4*156 == 624 bytes -/* initializes state[N] with a seed */ -void init_genrand(unsigned long s) -{ - int j; - state[0]= s & 0xffffffffUL; - for (j=1; j> 30)) + j); - /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */ - /* In the previous versions, MSBs of the seed affect */ - /* only MSBs of the array state[]. */ - /* 2002/01/09 modified by Makoto Matsumoto */ - state[j] &= 0xffffffffUL; /* for >32 bit machines */ - } - left = 1; initf = 1; -} +// Name of the device/file to seed the PRNG from +char * prng_device_name = NULL; -/* initialize by an array with array-length */ -/* init_key is the array for initializing keys */ -/* key_length is its length */ -/* slight change for C++, 2004/2/26 */ -void init_by_array(unsigned long init_key[], int key_length) -{ - int i, j, k; - init_genrand(19650218UL); - i=1; j=0; - k = (N>key_length ? N : key_length); - for (; k; k--) { - state[i] = (state[i] ^ ((state[i-1] ^ (state[i-1] >> 30)) * 1664525UL)) - + init_key[j] + j; /* non linear */ - state[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */ - i++; j++; - if (i>=N) { state[0] = state[N-1]; i=1; } - if (j>=key_length) j=0; - } - for (k=N-1; k; k--) { - state[i] = (state[i] ^ ((state[i-1] ^ (state[i-1] >> 30)) * 1566083941UL)) - - i; /* non linear */ - state[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */ - i++; - if (i>=N) { state[0] = state[N-1]; i=1; } - } - - state[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */ - left = 1; initf = 1; -} - -static void next_state(void) -{ - unsigned long *p=state; - int j; - - /* if init_genrand() has not been called, */ - /* a default initial seed is used */ - if (initf==0) init_genrand(5489UL); - - left = N; - next = state; - - for (j=N-M+1; --j; p++) - *p = p[M] ^ TWIST(p[0], p[1]); - - for (j=M; --j; p++) - *p = p[M-N] ^ TWIST(p[0], p[1]); - - *p = p[M-N] ^ TWIST(p[0], state[0]); -} - -/* generates a random number on [0,0xffffffff]-interval */ -unsigned long genrand_int32(void) -{ - unsigned long y; - - if (--left == 0) next_state(); - y = *next++; - - /* Tempering */ - y ^= (y >> 11); - y ^= (y << 7) & 0x9d2c5680UL; - y ^= (y << 15) & 0xefc60000UL; - y ^= (y >> 18); - - return y; -} - -#if 0 - -/** LDMud doesn't use the following functions - yet. **/ - -/* generates a random number on [0,0x7fffffff]-interval */ -long genrand_int31(void) -{ - unsigned long y; - - if (--left == 0) next_state(); - y = *next++; - - /* Tempering */ - y ^= (y >> 11); - y ^= (y << 7) & 0x9d2c5680UL; - y ^= (y << 15) & 0xefc60000UL; - y ^= (y >> 18); - - return (long)(y>>1); -} - -/* generates a random number on [0,1]-real-interval */ -double genrand_real1(void) -{ - unsigned long y; - - if (--left == 0) next_state(); - y = *next++; - - /* Tempering */ - y ^= (y >> 11); - y ^= (y << 7) & 0x9d2c5680UL; - y ^= (y << 15) & 0xefc60000UL; - y ^= (y >> 18); - - return (double)y * (1.0/4294967295.0); - /* divided by 2^32-1 */ -} - -/* generates a random number on [0,1)-real-interval */ -double genrand_real2(void) -{ - unsigned long y; - - if (--left == 0) next_state(); - y = *next++; - - /* Tempering */ - y ^= (y >> 11); - y ^= (y << 7) & 0x9d2c5680UL; - y ^= (y << 15) & 0xefc60000UL; - y ^= (y >> 18); - - return (double)y * (1.0/4294967296.0); - /* divided by 2^32 */ -} - -/* generates a random number on (0,1)-real-interval */ -double genrand_real3(void) -{ - unsigned long y; - - if (--left == 0) next_state(); - y = *next++; - - /* Tempering */ - y ^= (y >> 11); - y ^= (y << 7) & 0x9d2c5680UL; - y ^= (y << 15) & 0xefc60000UL; - y ^= (y >> 18); - - return ((double)y + 0.5) * (1.0/4294967296.0); - /* divided by 2^32 */ -} - -/* generates a random number on [0,1) with 53-bit resolution*/ -double genrand_res53(void) -{ - unsigned long a=genrand_int32()>>5, b=genrand_int32()>>6; - return(a*67108864.0+b)*(1.0/9007199254740992.0); -} -/* These real versions are due to Isaku Wada, 2002/01/09 added */ - -#endif - /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ /* Driver interface functions */ - /*-------------------------------------------------------------------------*/ -void -seed_random (uint32 seed) -/* Initialize the generator */ - -{ - unsigned long init[4]; - init[0] = seed & 0xFFF; - init[1] = (seed >>= 8) & 0xFFF; - init[2] = (seed >>= 8) & 0xFFF; - init[3] = (seed >>= 8) & 0xFFF; - init_by_array(init, 4); -} /* seed_random() */ - -/*-------------------------------------------------------------------------*/ -uint32 -random_number (uint32 n) - +/* random_number() is in random.h to be inlined. */ /* Return a random number in the range 0..n-1. * * The MT FAQ suggests: * If the application is not sensitive to the rounding off error, then please * multiply N to [0,1)-real uniform random numbers and take the integer part * (this is sufficient for most applications). - * + * I use the appropriate functions from the SFMT to generate random numbers on + * the [0,1) interval and multiply with N. */ +#if SIZEOF_LONG == SIZEOF_CHAR_P +uint64_t random_number(uint64_t n) { + return genrand_res53() * n; +} +#elif SIZEOF_INT == SIZEOF_CHAR_P +uint32_t random_number(uint32 n) { + return genrand_real2() * n; +} +#else +#error We currently do not yet support a 128 bit integer type used as \ + svalue number type. +#endif +void seed_random_from_int (uint32_t seed) +/* Initialize the generator */ + { - return genrand_int32() * (1.0/4294967296.0) * n; - /* - * Since most compilers compute the constant when it is compiled, so this - * code runs with the same speed with the standard C codes, and portability - * and readability are better. - */ -} /* random_number() */ + printf("%s Seeding PRNG with: 0x%lx\n" + , time_stamp(), (unsigned long)seed); + debug_message("%s Seeding PRNG with: 0x%lx\n" + , time_stamp(), (unsigned long)seed); + init_gen_rand(seed); +} /* seed_random_from_int() */ + +/*-------------------------------------------------------------------------*/ + +void +seed_random(const char *filename) + /* Opens the file given by filename and reads 156 uint32_t (624 + * bytes) from it (most often the file is probably /dev/urandom or + * /dev/random). If successful the random number generator will be seeded + * by an array of 624 bytes. Otherwise the driver clock will be used as + * fallback. + */ +{ + FILE *seedsrc = NULL; // Filepointer + + // If we got a NULL pointer or an empty string, don't try to open some + // device/file. + if (filename != NULL && strlen(filename)) + seedsrc = fopen(filename,"rb"); + + // if we have a file descriptor try to get a suitable amount of 32-bit + // values from a file (right now 156 uint32_t / 624 bytes) + if (seedsrc) { + uint32_t seeddata[INIT_ARRAY_SIZE]; + size_t count = fread( seeddata, sizeof(uint32), INIT_ARRAY_SIZE, + seedsrc ); + fclose(seedsrc); + if( count == INIT_ARRAY_SIZE ) { + init_by_array(seeddata, INIT_ARRAY_SIZE ); // seed PRNG + printf("%s Seeding PRNG from %s.\n", time_stamp(), + filename); + debug_message("%s Seeding PRG from %s.\n", time_stamp(), + filename); + return; + } // if (count == INIT_ARRAY_SIZE) + } // if (seedsrc) + + // Fall-back: driver clock + printf("%s Seeding PRNG with current driver time\n" + , time_stamp()); + debug_message("%s Seeding PRNG with current driver time\n" + , time_stamp()); + seed_random_from_int((uint32_t)current_time); + +} /* seed_random() */ + /***************************************************************************/ Index: src/random.h =================================================================== --- src/random.h (Revision 2461) +++ src/random.h (Arbeitskopie) @@ -2,8 +2,28 @@ #define RANDOM_H__ 1 #include "driver.h" +// SFTM expects MEXP to contain the desired period length +#ifdef RANDOM_PERIOD_LENGTH +#define MEXP RANDOM_PERIOD_LENGTH +#endif -extern uint32 random_number(uint32 n); -extern void seed_random(uint32 seed); +#include "random/SFMT.h" +#define PRNG_DEFAULT_DEVICE "/dev/urandom" + +// device/file to read seed for the PRNG from +extern char * prng_device_name; + +/* --- Prototypes --- */ +extern void seed_random_from_int(uint32_t seed); +extern void seed_random(const char *filename); +#if SIZEOF_LONG == SIZEOF_CHAR_P +uint64_t random_number(uint64_t n); +#elif SIZEOF_INT == SIZEOF_CHAR_P +uint32_t random_number(uint32_t n); +#else +#error We currently do not yes support a 128 bit integer type used as \ + svalue number type. +#endif + #endif /* RANDOM_H__ */ Index: src/config.h.in =================================================================== --- src/config.h.in (Revision 2461) +++ src/config.h.in (Arbeitskopie) @@ -141,6 +141,11 @@ */ #define MAX_MALLOCED @val_max_malloced@ +/* --- Random Number Generator (SFMT) --- */ +/* Set the period length of the SFMT. + * Default is a period length of 2^19937 - 1 + */ +#define RANDOM_PERIOD_LENGTH @val_random_period_length@ /* --- Interpreter --- */ Index: src/Makefile.in =================================================================== --- src/Makefile.in (Revision 2461) +++ src/Makefile.in (Arbeitskopie) @@ -71,6 +71,14 @@ # recompile. #DEBUG = -DDEBUG # -DDEBUG_TELNET DEBUG= + +# Flags for compiling the SFMT random number generator. +SFMT_FLAGS = -fno-strict-aliasing +# for machines with sse2 support you may use: +#SFMT_FLAGS = -msse2 -fno-strict-aliasing -DHAVE_SSE2=1 +# for machines with altivec support you may use: +#SFMT_FLAGS = -faltivec -fno-strict-aliasing -DHAVE_ALTIVEC=1 + # MPATH=-DMUD_LIB='"$(MUD_LIB)"' -DBINDIR='"$(BINDIR)"' -DERQ_DIR='"$(ERQ_DIR)"' # @@ -207,6 +215,9 @@ pcre/chartables.c : dftables@EXEEXT@ ./dftables@EXEEXT@ pcre/chartables.c +random.o : random.c config.h driver.h + $(CC) $(CFLAGS) $(SFMT_FLAGS) -c random.c -o random.o + #-------------------------------------------------------- # The dependency generation uses the program 'mkdepend' and assumes GNUmake. Index: src/efuns.c =================================================================== --- src/efuns.c (Revision 2461) +++ src/efuns.c (Arbeitskopie) @@ -8738,7 +8738,7 @@ if (sp->u.number <= 0) sp->u.number = 0; else - sp->u.number = (p_int)random_number((uint32)sp->u.number); + sp->u.number = (p_int)random_number(sp->u.number); return sp; } /* f_random() */ Index: src/main.c =================================================================== --- src/main.c (Revision 2461) +++ src/main.c (Arbeitskopie) @@ -114,8 +114,6 @@ Bool allow_filename_spaces = MY_FALSE; /* Allow spaces in filenames */ -static uint32 random_seed = 0; /* The seed for the pseudo-random generator. */ - static char * hostname = NULL; static char * hostaddr = NULL; /* Hostname and -addr given on the commandline. They are passed as @@ -281,9 +279,15 @@ put_number(&const1, 1); current_time = get_current_time(); - random_seed = (uint32)current_time; - seed_random(random_seed); - + + + // Set prng_device_name to the default // + prng_device_name = strdup(PRNG_DEFAULT_DEVICE); + // init PRG by the default device (/dev/urandom) + // if --random-seed or --randomdevice is given on the command-line it + // will re-seeded later. + seed_random(prng_device_name); + do { dummy_current_object_for_loads = NULL_object; #ifdef DEBUG @@ -437,11 +441,6 @@ for (i = 0; i < (int)(sizeof avg_consts / sizeof avg_consts[0]); i++) avg_consts[i] = exp(- i / 900.0); - printf("%s Random seed: 0x%lx\n" - , time_stamp(), (unsigned long)random_seed); - debug_message("%s Random seed: 0x%lx\n" - , time_stamp(), (unsigned long)random_seed); - #ifdef USE_MYSQL if (!pkg_mysql_init()) { @@ -1055,6 +1054,7 @@ , cNoHeart /* --no-heart */ , cNoPreload /* --no-preload */ , cPidFile /* --pidfile */ + , cRandomdevice /* --randomdevice */ , cRandomSeed /* --random-seed */ , cRegexp /* --regexp */ , cResetTime /* --reset-time */ @@ -1505,6 +1505,13 @@ " Write the pid of the driver process into .\n" } + , { 0, "randomdevice", cRandomdevice, MY_TRUE + , " --randomdevice \n" + , " --randomdevice \n" + " Determines the source of the seed for the random number generator.\n" + " (tries /dev/urandom by default and uses system clock as fallback)\n" + } + , { 0, "random-seed", cRandomSeed, MY_TRUE , " --random-seed \n" , " --random-seed \n" @@ -2539,14 +2546,23 @@ free(debug_file); debug_file = strdup(pValue); break; + + case cRandomdevice: + // sets prng_device_name to some file/device and re-seeds the PRNG + // from it. + if (prng_device_name != NULL) + free(prng_device_name); + prng_device_name = strdup(pValue); + seed_random(prng_device_name); + break; case cRandomSeed: + // seeds PRG with given value #ifdef HAVE_STRTOUL - random_seed = strtoul(pValue, (char **)0, 0); + seed_random_from_int(strtoul(pValue, (char **)0, 0)); #else - random_seed = (uint32)strtol(pValue, (char **)0, 0); + seed_random_from_int((uint32)strtol(pValue, (char **)0, 0)); #endif - seed_random(random_seed); break; case cReserved: