0000527: New version of the Mersenne Twister needed for 64 bit platforms

ID	Project	Category	View Status	Date Submitted	Last Update

0000527	LDMud 3.3	Portability	public	2008-01-27 14:28	2018-01-29 21:57

Reporter	zesstra	Assigned To	zesstra
Priority	normal	Severity	minor	Reproducibility	always
Status	resolved	Resolution	fixed
Platform	x86_64	OS	MacOS X	OS Version	10.5.x
Product Version	3.3
Fixed in Version	3.3.718

Summary	0000527: New version of the Mersenne Twister needed for 64 bit platforms
Description	The Mersenne Twister RNG uses a 32-bit word length. I think for 64-bit platforms we need the MT19937-64 with a 64-bit word length. Right now the drivers PRG is limited to the range of 0 - 2^32-1, which should be extended on 64-bit platforms. I will have a look at that later, but if anyone else has something ready, please feel free ;-)
Tags	No tags attached.
Attached Files	sfmt-V4.diff (79,385 bytes) 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 <filename> + Chooses the source of the seed for the random number generator. + Default is /dev/urandom, Fall-back if <filename> 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 <num> 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 <string.h> +#include <assert.h> +#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 <altivec.h> + #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 <emmintrin.h> + +/* 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 <stdio.h> + +#if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) + #include <inttypes.h> +#elif defined(_MSC_VER) \|\| defined(__BORLANDC__) + typedef unsigned int uint32_t; + typedef unsigned __int64 uint64_t; + #define inline __inline +#else + #include <inttypes.h> + #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; // 4156 == 624 bytes -/ initializes state[N] with a seed / -void init_genrand(unsigned long s) -{ - int j; - state[0]= s & 0xffffffffUL; - for (j=1; j<N; j++) { - state[j] = (1812433253UL (state[j-1] ^ (state[j-1] >> 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(a67108864.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 <filename>.\n" } + , { 0, "randomdevice", cRandomdevice, MY_TRUE + , " --randomdevice <filename>\n" + , " --randomdevice <filename>\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 <num>\n" , " --random-seed <num>\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: sfmt-V4.diff (79,385 bytes)

zesstra 2008-01-27 17:20 administrator ~0000593	I just had a look at the 64-bit version of the MT and read a note from its author. He states, that the SIMD-oriented Fast Mersenne Twister (SFMT), a variant of the MT, is much faster: "It is faster than the original MT, even in non-SIMD CPUs, and has better assurance of randomenss." The SFTM homepage states: "SFMT is much faster than MT, in most platforms. Not only the speed, but also the dimensions of equidistributions at v-bit precision are improved. In addition, recovery from 0-excess initial state is much faster." The license of SFMT is the same as for the original MT. Details can be found at: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html The speed comparisons look quite impressive. Has anyone an opinion about this?

zesstra 2008-05-07 13:50 administrator ~0000617	If there is nobody speaking against the SFMT, I would like to give it a shot and start working on a patch integrating it into the driver, with 32-bit and 64-bit variants and probably the optimized code for SSE2, Altivec and CPUs without both. Just to let you know. ;-)

zesstra 2008-05-09 16:43 administrator ~0000621	OK. First version of a patch which replaces the MT with the SFMT-1.3.3 and make the PRNG usable in 64-bit environments. random.c and random.h are a wrapper around the functions of the SFMT. The SFMT is contained in a new sub-directory src/random/, because it contains multiple Files for different period lengths and optimizations. random.c includes random/SFMT.c, so a number of functions should be inlinable by the compiler. I removed non-necessary files from the SFMT (like Makefile, most of the documention), but I didn't remove functions from the source, which we don't use. The reasoning behind this is, that it is easier to update the SFMT if we use their source more or less 'as is'. If it really disturbs someone, we may remove some public functions like get_idstring() and 2 functions which generate arrays of random numbers. I added a --with-random-period-length to autoconf/configure.in and a corresponding define to config.h.in for choosing the period length of the SFMT (default: 19937 -> 2^19937 - 1, supported are several length between 2^607-1 to 2^216091-1). Additionally the patch includes my changes for seeding the PRNG from /dev/urandom or /dev/random (see 0000515) which make it impossible to guess the seed and removes the problem that the 32-bit integer seed can only make 2^32 kinds of initial state. However there is something still missing: I did not mange until now to include the necessary autoconf magic to automatically set HAVE_SSE2 and -msse2 (and the corresponding altivec variants). If anybody has a working solution for this I would be delighted. ;-) If anybody is interested to test the patch, I will be happy about comments.

Gnomi 2008-07-01 02:35 manager ~0000638	The command line option --randominit seems somewhat limiting. Wouldn't it be better to specifiy the random device name itself? (And if it's missing stick to the system clock.) In random.c random.h should be included before random/SFMT.c, otherwise the definition of MEXP comes too late. I also got the following warning: random.c: In function 'seed_random': random.c:82: warning: passing argument 1 of 'init_by_array' from incompatible pointer type I can't comment on the SFMT itself, so go for it.

zesstra 2008-07-01 16:40 administrator ~0000648	Ok, the incompatible pointer type was due to use of uint32 in the driver and uint32_t in the SFMT, and I missed one. I use now in the random wrapper consistently uint32_t (and uint64_t). Generalizing --random-init is definitely a good idea, it can now be used to specify arbitrary filenames. (We may think about deprecating --random-seed as you could give a constant seed in a file. It would be nice to change the behaviour of -random-seed instead of introducing --random-init, but I don't know, if we can do that... ;-) Or maybe --random-device would also be appropriate.) Mhmm, what about adding a configure switch to specify the default filename/device to use for seeding the PRNG (defaulting to /dev/urandom?). If that is non-readable, the driver will use the clock as fallback as always, if the given file is non-readable. Setting the filename to an empty string would also cause the driver to use the system clock. One thing may be interesting as well: we could store the file name for the uptime and enable re-seeding the PRNG, e.g. by efun (specifying files similar to the garbage_collection() efun) or automatically at some point in the backend. BTW: any autoconf experts there, who know some working magic to enable HAVE_SSE2 and -msse2 (and the corresponding altivec variants)?

zesstra 2008-12-15 06:49 administrator ~0000821	Fuchur asked about the difference in performance between SSE2-optimized and non-optimized versions of the SFMT (I don't have any PowerPC available for Altivec). His idea was to skip any automatic detection of SSE stuff during configure and don't use any fancy compiler settings. Execution time for 300k numbers (including loop overhead): foreach(int i: 300000) random(__INT_MAX__); SFMT, i386: 172ms SFMT, x86_64 85ms SFMT-sse2, i386: 137ms SFMT-sse2, x86_64: 82ms As you see, there is no difference on x86_64 platforms. The reason is AFAIK, that on this platform gcc implicitely uses the SSE stuff, which is good news. On i386 platforms, there is a larger difference. Don't know, if it warrants the effort to find some autoconf magic... One odd thing: Old PRNG, i386: 101ms Old PRNG, x86_64 80ms As you see, the old PRNG ist actually faster than the new one. This should not be the case if you compare with the speed comparison the authors did: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/speed.html

zesstra 2009-01-03 15:48 administrator ~0000846	Im preparing the latest SFMT patch now and will probably apply it tomorrow. I added some improvements, e.g. changing the "public" functions of the the SFMT to static ones, because they are only used through the wrapper of the driver. Now the complete stuff of the PRG is inlined into one function (random_number). Timings for 1000k numbers (foreach(int i: 1000000) random(__INT_MAX__);) SFMT, 64: 285ms SFMT, 32: 550ms SFMT, 32-sse2: 470ms Alt, 64: 255ms Alt, 32: 475ms I am still curious about this unexpected increase in execution time, but I guess, it is not that significant... Most of the time (about 65-75%) is spent in eval_instruction() anyway (according to a statistical sampling while generating random numbers), see below. SFMT-32: - 64.4%, eval_instruction, ldmud.random - 12.7%, random_number, ldmud.random - 8.1%, check_object_shadow, ldmud.random - 4.1%, check_all_object_shadows, ldmud.random - 3.5%, int_free_svalue, ldmud.random - 3.5%, assert_stack_gap, ldmud.random - 2.7%, free_svalue, ldmud.random - 1.0%, f_random, ldmud.random SFMT-32-sse2: - 62.8%, eval_instruction, ldmud.random.sse2 - 12.1%, random_number, ldmud.random.sse2 - 9.4%, check_object_shadow, ldmud.random.sse2 - 4.6%, assert_stack_gap, ldmud.random.sse2 - 4.1%, free_svalue, ldmud.random.sse2 - 3.4%, check_all_object_shadows, ldmud.random.sse2 - 3.3%, int_free_svalue, ldmud.random.sse2 - 0.5%, f_random, ldmud.random.sse2 SFMT-64: - 71.6%, eval_instruction, ldmud64.random - 11.8%, random_number, ldmud64.random - 7.5%, assert_stack_gap, ldmud64.random - 4.3%, free_svalue, ldmud64.random - 3.8%, int_free_svalue, ldmud64.random - 1.0%, f_random, ldmud64.random MT-32: - 64.9%, eval_instruction, ldmud - 9.0%, check_object_shadow, ldmud - 6.6%, random_number, ldmud - 4.4%, assert_stack_gap, ldmud - 4.1%, int_free_svalue, ldmud - 3.8%, check_all_object_shadows, ldmud - 3.6%, genrand_int32, ldmud - 3.1%, free_svalue, ldmud - 0.6%, f_random, ldmud MT-64 - 75.2%, eval_instruction, ldmud64 - 7.9%, assert_stack_gap, ldmud64 - 4.1%, random_number, ldmud64 - 4.1%, free_svalue, ldmud64 - 3.9%, genrand_int32, ldmud64 - 3.4%, int_free_svalue, ldmud64 - 1.4%, f_random, ldmud64

zesstra 2009-01-04 13:33 administrator ~0000847	Committed as r2470.

Date Modified	Username	Field	Change
2008-01-27 14:28	zesstra	New Issue
2008-01-27 17:20	zesstra	Note Added: 0000593
2008-05-07 13:50	zesstra	Note Added: 0000617
2008-05-09 16:43	zesstra	Note Added: 0000621
2008-05-09 16:44	zesstra	File Added: sfmt-V1.diff
2008-06-30 02:54	zesstra	Status	new => assigned
2008-06-30 02:54	zesstra	Assigned To	=> zesstra
2008-07-01 02:35	Gnomi	Note Added: 0000638
2008-07-01 16:40	zesstra	Note Added: 0000648
2008-07-02 06:17	zesstra	Relationship added	related to 0000515
2008-07-13 12:02	zesstra	Relationship added	child of 0000555
2008-12-15 06:49	zesstra	Note Added: 0000821
2008-12-15 08:01	zesstra	File Deleted: sfmt-V1.diff
2008-12-15 08:01	zesstra	File Added: sfmt-V3.diff
2009-01-03 15:48	zesstra	Note Added: 0000846
2009-01-03 15:49	zesstra	File Added: sfmt-V4.diff
2009-01-03 15:49	zesstra	File Deleted: sfmt-V3.diff
2009-01-04 13:33	zesstra	Note Added: 0000847
2009-01-04 13:33	zesstra	Status	assigned => resolved
2009-01-04 13:33	zesstra	Fixed in Version	=> 3.3.718
2009-01-04 13:33	zesstra	Resolution	open => fixed
2010-11-16 09:42	zesstra	Source_changeset_attached	=> ldmud.git master e1fe0c90
2018-01-29 18:59	zesstra	Source_changeset_attached	=> ldmud.git master e1fe0c90
2018-01-29 21:57	zesstra	Source_changeset_attached	=> ldmud.git master e1fe0c90

View Issue Details

Relationships

Activities

Issue History

related to	0000515	resolved	zesstra	LDMud 3.3	Seeding the PRG with a more reliable source of randomness
child of	0000555	closed		LDMud 3.5	Complete support for 64bit (LP64) architectures