diff options
Diffstat (limited to 'src/inc/random.h')
| -rw-r--r-- | src/inc/random.h | 279 |
1 files changed, 279 insertions, 0 deletions
diff --git a/src/inc/random.h b/src/inc/random.h new file mode 100644 index 0000000000..cbf2d21c4e --- /dev/null +++ b/src/inc/random.h @@ -0,0 +1,279 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. +// +// random.h +// + +// +// Defines a random number generator, initially from the System.Random code in the BCL. If you notice any problems, +// please compare to the implementation in src\mscorlib\src\system\random.cs. +// +// Main advantages over rand() are: +// +// 1) It generates better random numbers +// 2) It can have multiple instantiations with different seeds +// 3) It behaves the same regardless of whether we build with VC++ or GCC +// +// If you are working in the VM, we have a convenience method: code:GetRandomInt. This usess a thread-local +// Random instance if a Thread object is available, and otherwise falls back to a global instance +// with a spin-lock. +// + +#ifndef _CLRRANDOM_H_ +#define _CLRRANDOM_H_ + +#include <math.h> + +// +// Forbid the use of srand()/rand(), as these are globally shared facilities and our use of them would +// interfere with native user code in the same process. This override is not compatible with stl headers. +// +#if !defined(DO_NOT_DISABLE_RAND) && !defined(USE_STL) + +#ifdef srand +#undef srand +#endif +#define srand Do_not_use_srand + +#ifdef rand +#undef rand +#endif +#define rand Do_not_use_rand + +#endif //!DO_NOT_DISABLE_RAND && !USE_STL + + +class CLRRandom +{ +private: + // + // Private Constants + // + static const int MBIG = INT_MAX; + static const int MSEED = 161803398; + static const int MZ = 0; + + + // + // Member Variables + // + int inext; + int inextp; + int SeedArray[56]; + + bool initialized; + +public: + // + // Constructors + // + + CLRRandom() + { + LIMITED_METHOD_CONTRACT; + initialized = false; + } + + void Init() + { + LIMITED_METHOD_CONTRACT; + LARGE_INTEGER time; + if (!QueryPerformanceCounter(&time)) + time.QuadPart = GetTickCount(); + Init((int)time.u.LowPart ^ GetCurrentThreadId() ^ GetCurrentProcessId()); + } + + void Init(int Seed) + { + LIMITED_METHOD_CONTRACT; + + int ii; + int mj, mk; + + //Initialize our Seed array. + mj = MSEED - abs(Seed); + SeedArray[55]=mj; + mk=1; + for (int i=1; i<55; i++) { //Apparently the range [1..55] is special (Knuth) and so we're wasting the 0'th position. + ii = (21*i)%55; + SeedArray[ii]=mk; + mk = mj - mk; + if (mk<0) mk+=MBIG; + mj=SeedArray[ii]; + } + for (int k=1; k<5; k++) { + for (int i=1; i<56; i++) { + SeedArray[i] -= SeedArray[1+(i+30)%55]; + if (SeedArray[i]<0) SeedArray[i]+=MBIG; + } + } + inext=0; + inextp = 21; + Seed = 1; + + initialized = true; + } + + bool IsInitialized() + { + LIMITED_METHOD_CONTRACT; + return initialized; + } + +private: + // + // Package Private Methods + // + + /*====================================Sample==================================== + **Action: Return a new random number [0..1) and reSeed the Seed array. + **Returns: A double [0..1) + **Arguments: None + **Exceptions: None + ==============================================================================*/ + double Sample() + { + LIMITED_METHOD_CONTRACT; + + //Including this division at the end gives us significantly improved + //random number distribution. + return (InternalSample()*(1.0/MBIG)); + } + + int InternalSample() + { + LIMITED_METHOD_CONTRACT; + + int retVal; + int locINext = inext; + int locINextp = inextp; + + if (++locINext >=56) locINext=1; + if (++locINextp>= 56) locINextp = 1; + + retVal = SeedArray[locINext]-SeedArray[locINextp]; + + if (retVal == MBIG) retVal--; + if (retVal<0) retVal+=MBIG; + + SeedArray[locINext]=retVal; + + inext = locINext; + inextp = locINextp; + + return retVal; + } + + double GetSampleForLargeRange() + { + LIMITED_METHOD_CONTRACT; + + // The distribution of double value returned by Sample + // is not distributed well enough for a large range. + // If we use Sample for a range [Int32.MinValue..Int32.MaxValue) + // We will end up getting even numbers only. + + int result = InternalSample(); + // Note we can't use addition here. The distribution will be bad if we do that. + bool negative = (InternalSample()%2 == 0) ? true : false; // decide the sign based on second sample + if( negative) { + result = -result; + } + double d = result; + d += (INT_MAX - 1); // get a number in range [0 .. 2 * Int32MaxValue - 1) + d /= 2*(unsigned int)INT_MAX - 1 ; + return d; + } + +public: + // + // Public Instance Methods + // + + + /*=====================================Next===================================== + **Returns: An int [0..Int32.MaxValue) + **Arguments: None + **Exceptions: None. + ==============================================================================*/ + int Next() + { + LIMITED_METHOD_CONTRACT; + _ASSERTE(initialized); + return InternalSample(); + } + + + /*=====================================Next===================================== + **Returns: An int [minvalue..maxvalue) + **Arguments: minValue -- the least legal value for the Random number. + ** maxValue -- One greater than the greatest legal return value. + **Exceptions: None. + ==============================================================================*/ + int Next(int minValue, int maxValue) + { + LIMITED_METHOD_CONTRACT; + _ASSERTE(initialized); + _ASSERTE(minValue < maxValue); + + LONGLONG range = (LONGLONG)maxValue-minValue; + double result; + + if( range <= (LONGLONG)INT_MAX) + result = (Sample() * range) + minValue; + else + result = (GetSampleForLargeRange() * range) + minValue; + + _ASSERTE(result >= minValue && result < maxValue); + return (int)result; + } + + + /*=====================================Next===================================== + **Returns: An int [0..maxValue) + **Arguments: maxValue -- One more than the greatest legal return value. + **Exceptions: None. + ==============================================================================*/ + int Next(int maxValue) + { + LIMITED_METHOD_CONTRACT; + _ASSERTE(initialized); + double result = Sample()*maxValue; + _ASSERTE(result >= 0 && result < maxValue); + return (int)result; + } + + + /*=====================================Next===================================== + **Returns: A double [0..1) + **Arguments: None + **Exceptions: None + ==============================================================================*/ + double NextDouble() + { + LIMITED_METHOD_CONTRACT; + _ASSERTE(initialized); + double result = Sample(); + _ASSERTE(result >= 0 && result < 1); + return result; + } + + + /*==================================NextBytes=================================== + **Action: Fills the byte array with random bytes [0..0x7f]. The entire array is filled. + **Returns:Void + **Arguments: buffer -- the array to be filled. + **Exceptions: None + ==============================================================================*/ + void NextBytes(__out_ecount(length) BYTE buffer[], int length) + { + LIMITED_METHOD_CONTRACT; + _ASSERTE(initialized); + for (int i=0; i<length; i++) { + buffer[i]=(BYTE)(InternalSample()%(256)); + } + } +}; + +#endif //_CLRRANDOM_H_ |