4
// $Id: //poco/1.2/Foundation/src/Random.cpp#3 $
10
// Definition of class Random.
12
// Copyright (c) 2004-2006, Applied Informatics Software Engineering GmbH.
15
// Permission is hereby granted, free of charge, to any person or organization
16
// obtaining a copy of the software and accompanying documentation covered by
17
// this license (the "Software") to use, reproduce, display, distribute,
18
// execute, and transmit the Software, and to prepare derivative works of the
19
// Software, and to permit third-parties to whom the Software is furnished to
20
// do so, all subject to the following:
22
// The copyright notices in the Software and this entire statement, including
23
// the above license grant, this restriction and the following disclaimer,
24
// must be included in all copies of the Software, in whole or in part, and
25
// all derivative works of the Software, unless such copies or derivative
26
// works are solely in the form of machine-executable object code generated by
27
// a source language processor.
29
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
30
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
31
// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
32
// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
33
// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
34
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
35
// DEALINGS IN THE SOFTWARE.
38
// Based on the FreeBSD random number generator.
39
// src/lib/libc/stdlib/random.c,v 1.25
41
// Copyright (c) 1983, 1993
42
// The Regents of the University of California. All rights reserved.
43
// Redistribution and use in source and binary forms, with or without
44
// modification, are permitted provided that the following conditions
46
// 1. Redistributions of source code must retain the above copyright
47
// notice, this list of conditions and the following disclaimer.
48
// 2. Redistributions in binary form must reproduce the above copyright
49
// notice, this list of conditions and the following disclaimer in the
50
// documentation and/or other materials provided with the distribution.
51
// 4. Neither the name of the University nor the names of its contributors
52
// may be used to endorse or promote products derived from this software
53
// without specific prior written permission.
55
// THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
56
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
57
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
58
// ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
59
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
60
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
61
// OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
62
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
63
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
64
// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
69
#include "Poco/Random.h"
70
#include "Poco/RandomStream.h"
77
* An improved random number generation package. In addition to the standard
78
* rand()/srand() like interface, this package also has a special state info
79
* interface. The initstate() routine is called with a seed, an array of
80
* bytes, and a count of how many bytes are being passed in; this array is
81
* then initialized to contain information for random number generation with
82
* that much state information. Good sizes for the amount of state
83
* information are 32, 64, 128, and 256 bytes. The state can be switched by
84
* calling the setstate() routine with the same array as was initiallized
85
* with initstate(). By default, the package runs with 128 bytes of state
86
* information and generates far better random numbers than a linear
87
* congruential generator. If the amount of state information is less than
88
* 32 bytes, a simple linear congruential R.N.G. is used.
90
* Internally, the state information is treated as an array of uint32_t's; the
91
* zeroeth element of the array is the type of R.N.G. being used (small
92
* integer); the remainder of the array is the state information for the
93
* R.N.G. Thus, 32 bytes of state information will give 7 ints worth of
94
* state information, which will allow a degree seven polynomial. (Note:
95
* the zeroeth word of state information also has some other information
96
* stored in it -- see setstate() for details).
98
* The random number generation technique is a linear feedback shift register
99
* approach, employing trinomials (since there are fewer terms to sum up that
100
* way). In this approach, the least significant bit of all the numbers in
101
* the state table will act as a linear feedback shift register, and will
102
* have period 2^deg - 1 (where deg is the degree of the polynomial being
103
* used, assuming that the polynomial is irreducible and primitive). The
104
* higher order bits will have longer periods, since their values are also
105
* influenced by pseudo-random carries out of the lower bits. The total
106
* period of the generator is approximately deg*(2**deg - 1); thus doubling
107
* the amount of state information has a vast influence on the period of the
108
* generator. Note: the deg*(2**deg - 1) is an approximation only good for
109
* large deg, when the period of the shift is the dominant factor.
110
* With deg equal to seven, the period is actually much longer than the
111
* 7*(2**7 - 1) predicted by this formula.
113
* Modified 28 December 1994 by Jacob S. Rosenberg.
114
* The following changes have been made:
115
* All references to the type u_int have been changed to unsigned long.
116
* All references to type int have been changed to type long. Other
117
* cleanups have been made as well. A warning for both initstate and
118
* setstate has been inserted to the effect that on Sparc platforms
119
* the 'arg_state' variable must be forced to begin on word boundaries.
120
* This can be easily done by casting a long integer array to char *.
121
* The overall logic has been left STRICTLY alone. This software was
122
* tested on both a VAX and Sun SpacsStation with exactly the same
123
* results. The new version and the original give IDENTICAL results.
124
* The new version is somewhat faster than the original. As the
125
* documentation says: "By default, the package runs with 128 bytes of
126
* state information and generates far better random numbers than a linear
127
* congruential generator. If the amount of state information is less than
128
* 32 bytes, a simple linear congruential R.N.G. is used." For a buffer of
129
* 128 bytes, this new version runs about 19 percent faster and for a 16
130
* byte buffer it is about 5 percent faster.
135
* For each of the currently supported random number generators, we have a
136
* break value on the amount of state information (you need at least this
137
* many bytes of state info to support this random number generator), a degree
138
* for the polynomial (actually a trinomial) that the R.N.G. is based on, and
139
* the separation between the two lower order coefficients of the trinomial.
141
#define TYPE_0 0 /* linear congruential */
146
#define TYPE_1 1 /* x**7 + x**3 + 1 */
151
#define TYPE_2 2 /* x**15 + x + 1 */
156
#define TYPE_3 3 /* x**31 + x**3 + 1 */
161
#define TYPE_4 4 /* x**63 + x + 1 */
170
Random::Random(int stateSize)
172
poco_assert (BREAK_0 <= stateSize && stateSize <= BREAK_4);
174
_pBuffer = new char[stateSize];
175
initState((UInt32) time(NULL), _pBuffer, stateSize);
186
* Compute x = (7^5 * x) mod (2^31 - 1)
187
* wihout overflowing 31 bits:
188
* (2^31 - 1) = 127773 * (7^5) + 2836
189
* From "Random number generators: good ones are hard to find",
190
* Park and Miller, Communications of the ACM, vol. 31, no. 10,
191
* October 1988, p. 1195.
193
inline UInt32 Random::goodRand(Int32 x)
197
if (x == 0) x = 123459876;
200
x = 16807 * lo - 2836 * hi;
201
if (x < 0) x += 0x7FFFFFFF;
208
* Initialize the random number generator based on the given seed. If the
209
* type is the trivial no-state-information type, just remember the seed.
210
* Otherwise, initializes state[] based on the given "seed" via a linear
211
* congruential generator. Then, the pointers are set to known locations
212
* that are exactly rand_sep places apart. Lastly, it cycles the state
213
* information a given number of times to get rid of any initial dependencies
214
* introduced by the L.C.R.N.G. Note that the initialization of randtbl[]
215
* for default usage relies on values produced by this routine.
217
void Random::seed(UInt32 x)
222
if (_randType == TYPE_0)
226
for (i = 1; i < _randDeg; i++)
227
_state[i] = goodRand(_state[i - 1]);
228
_fptr = &_state[_randSep];
232
for (i = 0; i < lim; i++)
238
* Many programs choose the seed value in a totally predictable manner.
239
* This often causes problems. We seed the generator using the much more
240
* secure random(4) interface. Note that this particular seeding
241
* procedure can generate states which are impossible to reproduce by
242
* calling srandom() with any value, since the succeeding terms in the
243
* state buffer are no longer derived from the LC algorithm applied to
250
if (_randType == TYPE_0)
251
len = sizeof _state[0];
253
len = _randDeg * sizeof _state[0];
255
RandomInputStream rstr;
256
rstr.read((char*) _state, len);
261
* Initialize the state information in the given array of n bytes for future
262
* random number generation. Based on the number of bytes we are given, and
263
* the break values for the different R.N.G.'s, we choose the best (largest)
264
* one we can and set things up for it. srandom() is then called to
265
* initialize the state information.
267
* Note that on return from srandom(), we set state[-1] to be the type
268
* multiplexed with the current value of the rear pointer; this is so
269
* successive calls to initstate() won't lose this information and will be
270
* able to restart with setstate().
272
* Note: the first thing we do is save the current state, if any, just like
273
* setstate() so that it doesn't matter when initstate is called.
275
* Returns a pointer to the old state.
277
* Note: The Sparc platform requires that arg_state begin on an int
278
* word boundary; otherwise a bus error will occur. Even so, lint will
279
* complain about mis-alignment, but you should disregard these messages.
281
void Random::initState(UInt32 s, char* argState, Int32 n)
283
UInt32* intArgState = (UInt32*) argState;
287
poco_bugcheck_msg("not enough state");
296
else if (n < BREAK_2)
302
else if (n < BREAK_3)
308
else if (n < BREAK_4)
320
_state = intArgState + 1; /* first location */
321
_endPtr = &_state[_randDeg]; /* must set end_ptr before seed */
323
if (_randType == TYPE_0)
324
intArgState[0] = _randType;
326
intArgState[0] = MAX_TYPES * (int) (_rptr - _state) + _randType;
333
* If we are using the trivial TYPE_0 R.N.G., just do the old linear
334
* congruential bit. Otherwise, we do our fancy trinomial stuff, which is
335
* the same in all the other cases due to all the global variables that have
336
* been set up. The basic operation is to add the number at the rear pointer
337
* into the one at the front pointer. Then both pointers are advanced to
338
* the next location cyclically in the table. The value returned is the sum
339
* generated, reduced to 31 bits by throwing away the "least random" low bit.
341
* Note: the code takes advantage of the fact that both the front and
342
* rear pointers can't wrap on the same call by not testing the rear
343
* pointer if the front one has wrapped.
345
* Returns a 31-bit random number.
347
UInt32 Random::next()
352
if (_randType == TYPE_0)
355
_state[0] = i = goodRand(i) & 0x7FFFFFFF;
360
* Use local variables rather than static variables for speed.
362
f = _fptr; r = _rptr;
364
i = (*f >> 1) & 0x7FFFFFFF; /* chucking least random bit */
365
if (++f >= _endPtr) {
369
else if (++r >= _endPtr) {
373
_fptr = f; _rptr = r;
added
removed
Foundation/src/Random.cpp
