skidd13@7935: /* $Id$ */ skidd13@7935: skidd13@7935: /** @file random_func.cpp */ skidd13@7935: skidd13@7935: #include "../stdafx.h" skidd13@7935: #include "random_func.hpp" rubidium@8113: #include "bitmath_func.hpp" skidd13@7935: rubidium@8434: Randomizer _random, _interactive_random; rubidium@8142: rubidium@8434: uint32 Randomizer::Next() skidd13@7935: { rubidium@8434: const uint32 s = this->state[0]; rubidium@8434: const uint32 t = this->state[1]; skidd13@7935: rubidium@8434: this->state[0] = s + ROR(t ^ 0x1234567F, 7) + 1; rubidium@8434: return this->state[1] = ROR(s, 3) - 1; skidd13@7935: } skidd13@7935: rubidium@8434: uint32 Randomizer::Next(uint16 max) skidd13@7935: { rubidium@8434: return GB(this->Next(), 0, 16) * max >> 16; rubidium@8434: } rubidium@8434: rubidium@8434: void Randomizer::SetSeed(uint32 seed) rubidium@8434: { rubidium@8434: this->state[0] = seed; rubidium@8434: this->state[1] = seed; skidd13@7935: } skidd13@7935: skidd13@7935: #ifdef MERSENNE_TWISTER skidd13@7935: // Source code for Mersenne Twister. skidd13@7935: // A Random number generator with much higher quality random numbers. skidd13@7935: skidd13@7935: #define N (624) // length of _mt_state vector skidd13@7935: #define M (397) // a period parameter skidd13@7935: #define K (0x9908B0DFU) // a magic constant skidd13@7935: #define hiBit(u) ((u) & 0x80000000U) // mask all but highest bit of u skidd13@7935: #define loBit(u) ((u) & 0x00000001U) // mask all but lowest bit of u skidd13@7935: #define loBits(u) ((u) & 0x7FFFFFFFU) // mask the highest bit of u skidd13@7935: #define mixBits(u, v) (hiBit(u)|loBits(v)) // move hi bit of u to hi bit of v skidd13@7935: skidd13@7935: static uint32 _mt_state[N+1]; // _mt_state vector + 1 extra to not violate ANSI C skidd13@7935: static uint32 *_mt_next; // _mt_next random value is computed from here skidd13@7935: static int _mt_left = -1; // can *_mt_next++ this many times before reloading skidd13@7935: skidd13@7935: void SetRandomSeed(register uint32 seed) skidd13@7935: { skidd13@7935: register uint32 *s = _mt_state; skidd13@7935: _mt_left = 0; skidd13@7935: skidd13@7935: seed |= 1U; skidd13@7935: seed &= 0xFFFFFFFFU; skidd13@7935: skidd13@7935: *s = seed; skidd13@7935: skidd13@7935: for (register uint i = N; i != 0; i--) { skidd13@7935: seed *= 69069U; skidd13@7935: *s++; skidd13@7935: *s = seed & 0xFFFFFFFFU; skidd13@7935: } skidd13@7935: } skidd13@7935: skidd13@7935: static uint32 ReloadRandom() skidd13@7935: { skidd13@7935: if (_mt_left < -1) SetRandomSeed(4357U); skidd13@7935: skidd13@7935: _mt_left = N - 1; skidd13@7935: _mt_next = _mt_state + 1; skidd13@7935: skidd13@7935: register uint32 *p0 = _mt_state; skidd13@7935: register uint32 *p2 = _mt_state + 2; skidd13@7935: register uint32 *pM = _mt_state + M; skidd13@7935: skidd13@7935: register uint32 s0 = _mt_state[0]; skidd13@7935: register uint32 s1 = _mt_state[1]; skidd13@7935: skidd13@7935: register uint i = 0; skidd13@7935: skidd13@7935: for (i = (N - M + 1); i != 0; i--) { skidd13@7935: s0 = s1; skidd13@7935: s1 = *p2; skidd13@7935: *p0 = *pM ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U); skidd13@7935: *p0++; skidd13@7935: *p2++; skidd13@7935: *pM++; skidd13@7935: } skidd13@7935: skidd13@7935: pM = _mt_state; skidd13@7935: skidd13@7935: for (i = M; i != 0; i--) { skidd13@7935: s0 = s1; skidd13@7935: s1 = *p2; skidd13@7935: *p0 = *pM ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U); skidd13@7935: *p0++; skidd13@7935: *p2++; skidd13@7935: *pM++; skidd13@7935: } skidd13@7935: skidd13@7935: s1 = _mt_state[0]; skidd13@7935: *p0 = *pM ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U); skidd13@7935: skidd13@7935: s1 ^= (s1 >> 11); skidd13@7935: s1 ^= (s1 << 7) & 0x9D2C5680U; skidd13@7935: s1 ^= (s1 << 15) & 0xEFC60000U; skidd13@7935: s1 ^= (s1 >> 18); skidd13@7935: return s1; skidd13@7935: } skidd13@7935: skidd13@7935: uint32 Random() skidd13@7935: { skidd13@7935: _mt_left--; skidd13@7935: if (_mt_left < 0) return ReloadRandom(); skidd13@7935: skidd13@7935: uint32 y = *_mt_next; skidd13@7935: *_mt_next++; skidd13@7935: skidd13@7935: y ^= (y >> 11); skidd13@7935: y ^= (y << 7) & 0x9D2C5680U; skidd13@7935: y ^= (y << 15) & 0xEFC60000U; skidd13@7935: y ^= (y >> 18); skidd13@7935: return y; skidd13@7935: } skidd13@7935: skidd13@7935: #else /* MERSENNE_TWISTER */ skidd13@7935: void SetRandomSeed(uint32 seed) skidd13@7935: { rubidium@8434: _random.SetSeed(seed); rubidium@8434: _interactive_random.SetSeed(seed * 0x1234567); skidd13@7935: } skidd13@7935: skidd13@7935: #ifdef RANDOM_DEBUG rubidium@8079: #include "../network/network_data.h" rubidium@8477: #include "../variables.h" /* _frame_counter */ rubidium@8477: #include "../player_func.h" rubidium@8477: skidd13@7935: uint32 DoRandom(int line, const char *file) skidd13@7935: { rubidium@8434: if (_networking && (DEREF_CLIENT(0)->status != STATUS_INACTIVE || !_network_server)) { skidd13@7935: printf("Random [%d/%d] %s:%d\n",_frame_counter, (byte)_current_player, file, line); rubidium@8434: } rubidium@8434: rubidium@8477: return _random.Next(); rubidium@8434: } skidd13@7935: #endif /* RANDOM_DEBUG */ skidd13@7935: #endif /* MERSENNE_TWISTER */ skidd13@7935: skidd13@7935: #if defined(RANDOM_DEBUG) && !defined(MERSENNE_TWISTER) skidd13@7935: uint DoRandomRange(uint max, int line, const char *file) skidd13@7935: { skidd13@7935: return GB(DoRandom(line, file), 0, 16) * max >> 16; skidd13@7935: } skidd13@7935: #endif /* RANDOM_DEBUG & !MERSENNE_TWISTER */