/* librock_CHISEL _summary Good pseudo-random number generator */ #ifdef librock_NOTLIBROCK /**************************************************************/ /* ABOUT THIS FILE: GUIDE TO QUICK REUSE WITHOUT REWORK This file uses many preprocessor conditional blocks and features to publish http://www.mibsoftware.com/librock/ You can disable those features with little or no editing, and reuse this file: 1. At compile time, enable this conditional block by defining the preprocessor symbol librock_NOTLIBROCK, either with a compiler command line parameter, or as a #define in a source file which then #includes this source file. 2. Define any preprocessor symbols in this block (if any) appropriately for your machine and compilation environment. 3. Copy and use the declarations from this block in your source files as appropriate. This file is originally from the librock library, which is Free (libre), free (no cost), rock-stable API, and works on gcc/MSVC/Windows/Linux/BSD/more. Get originals, updates, license certificates, more, at http://www.mibsoftware.com/librock/ (Change log appears at end of this file.) */ #define librock_ISOLATED #define librock_PTR #define librock_CONST const #define librock_PRIVATE static #include #include #include #define librock_uint32_t long librock_uint32_t librock_random(struct librock_random_s *state); /**************************************************************/ #endif #ifndef librock_ISOLATED /**************************************************************/ #define librock_IMPLEMENT_random #include #include #include #include #include #define uint32_t librock_uint32_t /**************************************************************/ #endif #ifdef librock_IMPL_LIDESC #ifndef librock_NOIMPL_LIDESC_random /**************************************************************/ #include /* librock_LIDESC_HC=526b72abf87ca6429325f0b7b0ae8dab0986c030 */ #include /* librock_LIDESC_HC=12440211096131f5976d36be0cddca4cd9152e45 */ char *librock_LIDESC_random[] = { "\n" __FILE__ librock_LIDESC_bsdorig "\n", "\n" __FILE__ librock_LIDESC_librock "\n", 0 }; /**************************************************************/ #endif #endif /* * Copyright (c) 1983 Regents of the University of California. * 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. All advertising materials mentioning features or use of this software * must display the following acknowledgement: * This product includes software developed by the University of * California, Berkeley and its contributors. * 4. Neither the name of the 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 REGENTS 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 REGENTS 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. */ /* For modified portions: Copyright (c) 2001-2002, Forrest J. Cavalier III, doing business as Mib Software, Saylorsburg Pennsylvania USA 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 author 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 REGENTS 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. */ #if defined(LIBC_SCCS) && !defined(lint) #ifndef librock_NOIMPL_rcsid librock_PRIVATE char *rcsid = "$OpenBSD: random.c,v 1.9 2000/04/04 14:27:00 millert Exp $"; #endif #endif /* LIBC_SCCS and not lint */ #ifndef librock_WRAP /* Function wrapping and tracing features are documented at http://www.mibsoftware.com/librock/ */ /**************************************************************/ #define librock_body_srandom librock_srandom #define librock_body_random librock_random /**************************************************************/ #endif #ifdef librock_MANUAL_random /* librock_random - Multithread-capable pseudo-random number generator. librock_srandom - Initialization routine for librock_random data. */ /**/ #include #include uint32_t librock_random(struct librock_random_s *state); struct librock_random_s * librock_srandom( struct librock_random_s *state, /* Pointer to state, or NULL */ uint32_t x, /* Random seed value */ char *prand, /* Random data for state, or NULL */ int n); /* Amount of state information */ /* This random number generation package is adapted from OpenBSD libc/random.c, (The code is originally from BSD 4.2.) The output and behavior is identical, but the calling conventions were modified to take a pointer to state information as an argument. This efficiently supports multiple concurrent state information blocks within a single process, without the inefficient copying of the original BSD setstate() routine. Typical use would be to generate pseudo-random streams for games or repeatable tests. See below for typical code. librock_random() returns a 31-bit random number, in a determined sequence set by the starting seed and initial state. The first argument is a pointer to the state information, which can be NULL to use an internal (static) block with 128 bytes of state, matching the BSD 4.2 output. Otherwise it should be a pointer previously given or returned from a call to librock_srandom(). librock_srandom intializes state information. When the first parameter is NULL, this will malloc() space, and the caller is responsible for calling free(). The number of bytes for static or external allocations of state information is #define'd as librock_SIZEOF_random_s in the header file. Since other pointers and values are kept in the state information block, it is not compatible with the BSD setstate() and initstate() routines. The parameter n, for the amount of state information is rounded down to the closest or equal value of 1, 32, 64, 128, and 256. (Using 1 is not recommended, even though it is fastest.) The values larger than 1 are equally efficient, but larger values keep more state and have a longer period without repeating.) The return value is NULL on error, or the pointer to the state information block. prand is an optional pointer to a block of n bytes of random data used to initialize the state. If prand is NULL, the seed value x (or 1 if the seed is 0) is used to initialize the state. The multi-threaded caller must perform locking when there could be concurrent calls with the same state pointer argument. The random number generation technique is a linear feedback shift register approach, employing trinomials (since there are fewer terms to sum up that way). In this approach, the least significant bit of all the numbers in the state table will act as a linear feedback shift register, and will have period 2^deg - 1 (where deg is the degree of the polynomial being used, assuming that the polynomial is irreducible and primitive). The higher order bits will have longer periods, since their values are also influenced by pseudo-random carries out of the lower bits. The total period of the generator is approximately deg*(2**deg - 1); thus doubling the amount of state information has a vast influence on the period of the generator. Note: the deg*(2**deg - 1) is an approximation only good for large deg, when the period of the shift register is the dominant factor. With deg equal to seven, the period is actually much longer than the 7*(2**7 - 1) predicted by this formula. To generate a uniformly distributed pseudo-random integer in the range 0,(N-1) inclusive when N <= 2^31, you could use the following. (If N is unchanging, precalculation of maxuniform will save time.) */ #ifdef librock_TYPICAL_USE_random #include #include struct librock_random_s *pstate; int N = 8000; pstate = librock_srandom(0,0x1234,0,0); if (N > 0) { long maxuniform = 0x8000000 - (0x80000000 % N); long r; do { r = librock_random(pstate); } while (r >= maxuniform); r %= N; printf("%ld\n",r); } #endif /* To generate a uniformly distributed pseudo-random floating point in the range 0 to N, you could use the following. (If N is unchanging, precalculation of a term will save time.) */ #ifdef librock_TYPICAL_USE_2_random printf("%g\n",(double) librock_random(0) * (N / (double) 0x80000000)); #endif /* The original BSD 4.2 code included a srandomdev() routine which seeded the generator with random data. Getting good random seed data for security purposes is a hard problem. Picking clocks (even microsecond clocks) would enable attackers to have a small search space. For reference the OpenBSD srandomdev() code tried to read from /dev/arandom/, and failing that would use the very less strong gettimeofday(). */ /* malloc() // librock_srandom if argument is 0 ldiv // librock_srandom memcpy // librock_srandom if prand is not 0 */ /* Copyright (c) 1983 Regents of the University of California. License text in librock_LIDESC_HC=526b72abf87ca6429325f0b7b0ae8dab0986c030 Licensed under BSD-ish license, NO WARRANTY. Copies must retain this block. Modifications Copyright (c) 2001 Forrest J. Cavalier III d-b-a Mib Software License text in librock_LIDESC_HC=12440211096131f5976d36be0cddca4cd9152e45 */ #endif /* MANUAL */ #ifndef librock_NOIMPL_TYPE_0 /* * For each of the currently supported random number generators, we have a * break value on the amount of state information (you need at least this * many bytes of state info to support this random number generator), a degree * for the polynomial (actually a trinomial) that the R.N.G. is based on, and * the separation between the two lower order coefficients of the trinomial. */ #define TYPE_0 0 /* linear congruential */ #endif #ifndef librock_NOIMPL_BREAK_0 #define BREAK_0 8 #endif #ifndef librock_NOIMPL_DEG_0 #define DEG_0 0 #endif #ifndef librock_NOIMPL_SEP_0 #define SEP_0 0 #endif #ifndef librock_NOIMPL_TYPE_1 #define TYPE_1 1 /* x**7 + x**3 + 1 */ #endif #ifndef librock_NOIMPL_BREAK_1 #define BREAK_1 32 #endif #ifndef librock_NOIMPL_DEG_1 #define DEG_1 7 #endif #ifndef librock_NOIMPL_SEP_1 #define SEP_1 3 #endif #ifndef librock_NOIMPL_TYPE_2 #define TYPE_2 2 /* x**15 + x + 1 */ #endif #ifndef librock_NOIMPL_BREAK_2 #define BREAK_2 64 #endif #ifndef librock_NOIMPL_DEG_2 #define DEG_2 15 #endif #ifndef librock_NOIMPL_SEP_2 #define SEP_2 1 #endif #ifndef librock_NOIMPL_TYPE_3 #define TYPE_3 3 /* x**31 + x**3 + 1 */ #endif #ifndef librock_NOIMPL_BREAK_3 #define BREAK_3 128 #endif #ifndef librock_NOIMPL_DEG_3 #define DEG_3 31 #endif #ifndef librock_NOIMPL_SEP_3 #define SEP_3 3 #endif #ifndef librock_NOIMPL_TYPE_4 #define TYPE_4 4 /* x**63 + x + 1 */ #endif #ifndef librock_NOIMPL_BREAK_4 #define BREAK_4 256 #endif #ifndef librock_NOIMPL_DEG_4 #define DEG_4 63 #endif #ifndef librock_NOIMPL_SEP_4 #define SEP_4 1 #endif #ifndef librock_NOIMPL_MAX_TYPES /* * Array versions of the above information to make code run faster -- * relies on fact that TYPE_i == i. */ #define MAX_TYPES 5 /* max number of types above */ #endif #ifndef librock_NOIMPL_degrees librock_PRIVATE int degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }; #endif #ifndef librock_NOIMPL_seps librock_PRIVATE int seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }; #endif #ifndef librock_NOIMPL_random_s /***************************************************************/ struct librock_random_s { /* * fptr and rptr are two pointers into the state info, a front and a rear * pointer. These two pointers are always rand_sep places aparts, as they * cycle cyclically through the state information. (Yes, this does mean we * could get away with just one pointer, but the code for random() is more * efficient this way). The pointers are left positioned as they would be * from the call * * initstate(1, randtbl, 128); * * (The position of the rear pointer, rptr, is really 0 (as explained above * in the initialization of randtbl) because the state table pointer is set * to point to randtbl[1] (as explained below). */ int rand_type; int rand_deg; int rand_sep; librock_uint32_t *fptr; librock_uint32_t *rptr; librock_uint32_t *end_ptr; librock_uint32_t randtbl[DEG_4]; /* Yes DEG_4, even though default is DEG_3 */ }; /***************************************************************/ #endif #ifndef librock_NOIMPL_random_default_state /***************************************************************/ /* * Initially, everything is set up as if from: * * initstate(1, &randtbl, 128); * * Note that this initialization takes advantage of the fact that srandom() * advances the front and rear pointers 10*rand_deg times, and hence the * rear pointer which starts at 0 will also end up at zero; thus the zeroeth * element of the state information, which contains info about the current * position of the rear pointer is just * * MAX_TYPES * (rptr - state) + TYPE_3 == TYPE_3. */ librock_PRIVATE struct librock_random_s default_state = { TYPE_3, DEG_3, SEP_3, &default_state.randtbl[SEP_3], &default_state.randtbl[0], &default_state.randtbl[DEG_3], { 0x991539b1, 0x16a5bce3, 0x6774a4cd, 0x3e01511e, 0x4e508aaa, 0x61048c05, 0xf5500617, 0x846b7115, 0x6a19892c, 0x896a97af, 0xdb48f936, 0x14898454, 0x37ffd106, 0xb58bff9c, 0x59e17104, 0xcf918a49, 0x09378c83, 0x52c7a471, 0x8d293ea9, 0x1f4fc301, 0xc3db71be, 0x39b44e1c, 0xf8a44ef9, 0x4c8b80b1, 0x19edc328, 0x87bf4bdd, 0xc9b240e5, 0xe9ee4b1b, 0x4382aee7, 0x535b6b41, 0xf3bec5da, } }; /***************************************************************/ #endif #ifndef librock_NOIMPL_srandom /***************************************************************/ /* * srandom: * * Initialize the random number generator based on the given seed. If the * type is the trivial no-state-information type, just remember the seed. * Otherwise, initializes state[] based on the given "seed" via a linear * congruential generator. Then, the pointers are set to known locations * that are exactly rand_sep places apart. Lastly, it cycles the state * information a given number of times to get rid of any initial dependencies * introduced by the L.C.R.N.G. Note that the initialization of randtbl[] * for default usage relies on values produced by this routine. */ struct librock_random_s * librock_body_srandom(struct librock_random_s *state, librock_uint32_t x, char *prand, int n) { /* Copyright (c) 1983 Regents of the University of California. Modifications Copyright (c) 2001 Forrest J. Cavalier III d-b-a Mib Software Licensed under BSD-ish license, NO WARRANTY. Copies must retain this block. License, originals, details: http://www.mibsoftware.com/librock/ */ register long int test; register int i; ldiv_t val; if (!state) { state = malloc(sizeof(struct librock_random_s *)); if (!state) { return NULL; } } if (n < BREAK_0) { return(NULL); } if (n < BREAK_1) { state->rand_type = TYPE_0; state->rand_deg = DEG_0; state->rand_sep = SEP_0; } else if (n < BREAK_2) { state->rand_type = TYPE_1; state->rand_deg = DEG_1; state->rand_sep = SEP_1; } else if (n < BREAK_3) { state->rand_type = TYPE_2; state->rand_deg = DEG_2; state->rand_sep = SEP_2; } else if (n < BREAK_4) { state->rand_type = TYPE_3; state->rand_deg = DEG_3; state->rand_sep = SEP_3; } else { state->rand_type = TYPE_4; state->rand_deg = DEG_4; state->rand_sep = SEP_4; } state->end_ptr = &state->randtbl[state->rand_deg]; /* must set end_ptr before srandom */ if (x == 0) { x++; } if (state->rand_type == TYPE_0) { state->randtbl[0] = x; } else { state->randtbl[0] = x; for (i = 1; i < state->rand_deg; i++) { /* * Implement the following, without overflowing 31 bits: * * state[i] = (16807 * state[i - 1]) % 2147483647; * * 2^31-1 (prime) = 2147483647 = 127773*16807+2836 */ val = ldiv(state->randtbl[i-1], 127773); test = 16807 * val.rem - 2836 * val.quot; state->randtbl[i] = test + (test < 0 ? 2147483647 : 0); } state->fptr = &state->randtbl[state->rand_sep]; state->rptr = &state->randtbl[0]; for (i = 0; i < 10 * state->rand_deg; i++) (void)librock_random(state); } if (prand) { memcpy(state->randtbl,prand,state->rand_deg); } return state; } /***************************************************************/ #endif /* librock_NOIMPL_srandom */ #ifndef librock_NOIMPL_random /***************************************************************/ /* * random: * * If we are using the trivial TYPE_0 R.N.G., just do the old linear * congruential bit. Otherwise, we do our fancy trinomial stuff, which is * the same in all the other cases due to all the global variables that have * been set up. The basic operation is to add the number at the rear pointer * into the one at the front pointer. Then both pointers are advanced to * the next location cyclically in the table. The value returned is the sum * generated, reduced to 31 bits by throwing away the "least random" low bit. * * Note: the code takes advantage of the fact that both the front and * rear pointers can't wrap on the same call by not testing the rear * pointer if the front one has wrapped. * * Returns a 31-bit random number. */ librock_uint32_t librock_body_random(struct librock_random_s *state) { /* Copyright (c) 1983 Regents of the University of California. Modifications Copyright (c) 2001 Forrest J. Cavalier III d-b-a Mib Software Licensed under BSD-ish license, NO WARRANTY. Copies must retain this block. License, originals, details: http://www.mibsoftware.com/librock/ */ long i; if (!state) { state = &default_state; } if (state->rand_type == TYPE_0) { /* This overflows 32 bits, but is the historical representation. FreeBSD has a correction, but no one should be using TYPE_0 anyway. -mibsoftware 2001-10-22 */ i = state->randtbl[0] = (state->randtbl[0] * 1103515245 + 12345) & 0x7fffffff; } else { *state->fptr += *state->rptr; i = (*state->fptr >> 1) & 0x7fffffff; /* chucking least random bit */ if (++(state->fptr) >= state->end_ptr) { state->fptr = state->randtbl; ++(state->rptr); } else if (++(state->rptr) >= state->end_ptr) state->rptr = state->randtbl; } return(i); } /***************************************************************/ #endif /* librock_NOIMPL_random */ /* $Log: random.c,v $ Revision 1.5 2002/08/01 19:46:34 forrest@mibsoftware.com rights=#1 Updated TYPICAL_USE section. Added NOTLIBROCK section. Moved CVS log to end. Changed LIDESC MD5 to HC. Revision 1.4 2002/04/09 03:29:54 forrest@mibsoftware.com rights=#1 FNTYPEs. Updated LICENSE in manual. Revision 1.3 2002/02/08 12:52:12 forrest@mibsoftware.com rights=#1 Standardized chg log Revision 1.2 2002/01/30 16:08:15 forrest@mibsoftware.com rights=#1 Renamed some .h files Revision 1.1 2002/01/29 04:46:30 forrest@mibsoftware.com rights=#1 Initial. Revamped API for pseudo-random number generation for librock rights#1 Copyright (c) Forrest J Cavalier III d-b-a Mib Software rights#1 License text in librock_LIDESC_HC=12440211096131f5976d36be0cddca4cd9152e45 librock_ACQUIRED: From source from OpenBSD project derived from BSD. Copyright (c) 1983 Regents of the University of California. */