X-Git-Url: https://git.artsoft.org/?a=blobdiff_plain;f=src%2Flibgame%2Frandom.c;h=fd409d06d8a7b3f808f162cd42f30cbee8a017d8;hb=HEAD;hp=864f3dcc902388e61c73239ac3662fb8893c2911;hpb=da14f69fd95c7bd5a0d70cdf4935af06f1f20a04;p=rocksndiamonds.git diff --git a/src/libgame/random.c b/src/libgame/random.c index 864f3dcc..fd409d06 100644 --- a/src/libgame/random.c +++ b/src/libgame/random.c @@ -1,3 +1,17 @@ +// ============================================================================ +// Artsoft Retro-Game Library +// ---------------------------------------------------------------------------- +// (c) 1995-2014 by Artsoft Entertainment +// Holger Schemel +// info@artsoft.org +// https://www.artsoft.org/ +// ---------------------------------------------------------------------------- +// random.c +// ============================================================================ + +#include "random.h" + + /* * Copyright (c) 1983 Regents of the University of California. * All rights reserved. @@ -25,8 +39,6 @@ #include #include -#include "random.h" - /* An improved random number generation package. In addition to the standard rand()/srand() like interface, this package also has a special state info @@ -116,7 +128,7 @@ position of the rear pointer is just (MAX_TYPES * (rptr - state)) + TYPE_3 == TYPE_3. */ -static long int randtbl[DEG_3 + 1] = +static int randtbl_0[DEG_3 + 1] = { TYPE_3, -851904987, -43806228, -2029755270, 1390239686, -1912102820, @@ -126,6 +138,17 @@ static long int randtbl[DEG_3 + 1] = -607508183, -205999574, -1696891592, 1492211999, -1528267240, -952028296, -189082757, 362343714, 1424981831, 2039449641, }; +static int randtbl_1[DEG_3 + 1] = +{ + TYPE_3, + -851904987, -43806228, -2029755270, 1390239686, -1912102820, + -485608943, 1969813258, -1590463333, -1944053249, 455935928, 508023712, + -1714531963, 1800685987, -2015299881, 654595283, -1149023258, + -1470005550, -1143256056, -1325577603, -1568001885, 1275120390, + -607508183, -205999574, -1696891592, 1492211999, -1528267240, + -952028296, -189082757, 362343714, 1424981831, 2039449641, +}; + /* 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 @@ -137,8 +160,8 @@ static long int randtbl[DEG_3 + 1] = in the initialization of randtbl) because the state table pointer is set to point to randtbl[1] (as explained below).) */ -static long int *fptr = &randtbl[SEP_3 + 1]; -static long int *rptr = &randtbl[1]; +static int *fptr[2] = { &randtbl_0[SEP_3 + 1], &randtbl_1[SEP_3 + 1] }; +static int *rptr[2] = { &randtbl_0[1], &randtbl_1[1] }; @@ -152,13 +175,17 @@ static long int *rptr = &randtbl[1]; indexing every time to find the address of the last element to see if the front and rear pointers have wrapped. */ -static long int *state = &randtbl[1]; +static int *state[2] = { &randtbl_0[1], &randtbl_1[1] }; -static int rand_type = TYPE_3; -static int rand_deg = DEG_3; -static int rand_sep = SEP_3; +static int rand_type[2] = { TYPE_3, TYPE_3 }; +static int rand_deg[2] = { DEG_3, DEG_3 }; +static int rand_sep[2] = { SEP_3, SEP_3 }; -static long int *end_ptr = &randtbl[sizeof(randtbl) / sizeof(randtbl[0])]; +static int *end_ptr[2] = +{ + &randtbl_0[sizeof(randtbl_0) / sizeof(randtbl_0[0])], + &randtbl_1[sizeof(randtbl_1) / sizeof(randtbl_1[0])] +}; /* Initialize the random number generator based on the given seed. If the type is the trivial no-state-information type, just remember the seed. @@ -169,18 +196,22 @@ static long int *end_ptr = &randtbl[sizeof(randtbl) / sizeof(randtbl[0])]; introduced by the L.C.R.N.G. Note that the initialization of randtbl[] for default usage relies on values produced by this routine. */ -void srandom_linux_libc(unsigned int x) +void srandom_linux_libc(int nr, unsigned int x) { - state[0] = x; - if (rand_type != TYPE_0) + state[nr][0] = x; + + if (rand_type[nr] != TYPE_0) { - register long int i; - for (i = 1; i < rand_deg; ++i) - state[i] = (1103515145 * state[i - 1]) + 12345; - fptr = &state[rand_sep]; - rptr = &state[0]; - for (i = 0; i < 10 * rand_deg; ++i) - (void) random_linux_libc(); + register int i; + + for (i = 1; i < rand_deg[nr]; ++i) + state[nr][i] = (1103515145 * state[nr][i - 1]) + 12345; + + fptr[nr] = &state[nr][rand_sep[nr]]; + rptr[nr] = &state[nr][0]; + + for (i = 0; i < 10 * rand_deg[nr]; ++i) + random_linux_libc(nr); } } @@ -195,31 +226,306 @@ void srandom_linux_libc(unsigned int x) 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. */ -long int random_linux_libc() +int random_linux_libc(int nr) { - if (rand_type == TYPE_0) + if (rand_type[nr] == TYPE_0) { - state[0] = ((state[0] * 1103515245) + 12345) & LONG_MAX; - return state[0]; + state[nr][0] = ((state[nr][0] * 1103515245) + 12345) & INT_MAX; + return state[nr][0]; } else { - long int i; - *fptr += *rptr; + int i; + + *fptr[nr] += *rptr[nr]; + /* Chucking least random bit. */ - i = (*fptr >> 1) & LONG_MAX; - ++fptr; - if (fptr >= end_ptr) + i = (*fptr[nr] >> 1) & INT_MAX; + fptr[nr]++; + + if (fptr[nr] >= end_ptr[nr]) { - fptr = state; - ++rptr; + fptr[nr] = state[nr]; + rptr[nr]++; } else { - ++rptr; - if (rptr >= end_ptr) - rptr = state; + rptr[nr]++; + if (rptr[nr] >= end_ptr[nr]) + rptr[nr] = state[nr]; } + return i; } } + + +// ============================================================================ + +/* + * prng.c - Portable, ISO C90 and C99 compliant high-quality + * pseudo-random number generator based on the alleged RC4 + * cipher. This PRNG should be suitable for most general-purpose + * uses. Not recommended for cryptographic or financial + * purposes. Not thread-safe. + */ + +/* + * Copyright (c) 2004 Ben Pfaff . + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. + * + */ + +#include +#include +#include +#include +#include + +/* RC4-based pseudo-random state. */ +static unsigned char s[256]; +static int s_i, s_j; + +/* Nonzero if PRNG has been seeded. */ +static int seeded; + +/* Swap bytes that A and B point to. */ +#define SWAP_BYTE(A, B) \ + do { \ + unsigned char swap_temp = *(A); \ + *(A) = *(B); \ + *(B) = swap_temp; \ + } while (0) + +/* Seeds the pseudo-random number generator based on the current + time. + + If the user calls neither this function nor prng_seed_bytes() + before any prng_get*() function, this function is called + automatically to obtain a time-based seed. */ +void +prng_seed_time (void) +{ + static time_t t; + if (t == 0) + t = time (NULL); + else + t++; + + prng_seed_bytes (&t, sizeof t); +} + +/* Retrieves one octet from the array BYTES, which is N_BYTES in + size, starting at an offset of OCTET_IDX octets. BYTES is + treated as a circular array, so that accesses past the first + N_BYTES bytes wrap around to the beginning. */ +static unsigned char +get_octet (const void *bytes_, size_t n_bytes, size_t octet_idx) +{ + const unsigned char *bytes = bytes_; + if (CHAR_BIT == 8) + return bytes[octet_idx % n_bytes]; + else + { + size_t first_byte = octet_idx * 8 / CHAR_BIT % n_bytes; + size_t start_bit = octet_idx * 8 % CHAR_BIT; + unsigned char c = (bytes[first_byte] >> start_bit) & 255; + + size_t bits_filled = CHAR_BIT - start_bit; + if (CHAR_BIT % 8 != 0 && bits_filled < 8) + { + size_t bits_left = 8 - bits_filled; + unsigned char bits_left_mask = (1u << bits_left) - 1; + size_t second_byte = first_byte + 1 < n_bytes ? first_byte + 1 : 0; + + c |= (bytes[second_byte] & bits_left_mask) << bits_filled; + } + + return c; + } +} + +/* Seeds the pseudo-random number based on the SIZE bytes in + KEY. At most the first 2048 bits in KEY are used. */ +void +prng_seed_bytes (const void *key, size_t size) +{ + int i, j; + + assert (key != NULL && size > 0); + + for (i = 0; i < 256; i++) + s[i] = i; + for (i = j = 0; i < 256; i++) + { + j = (j + s[i] + get_octet (key, size, i)) & 255; + SWAP_BYTE (s + i, s + j); + } + + s_i = s_j = 0; + seeded = 1; +} + +/* Returns a pseudo-random integer in the range [0, 255]. */ +unsigned char +prng_get_octet (void) +{ + if (!seeded) + prng_seed_time (); + + s_i = (s_i + 1) & 255; + s_j = (s_j + s[s_i]) & 255; + SWAP_BYTE (s + s_i, s + s_j); + + return s[(s[s_i] + s[s_j]) & 255]; +} + +/* Returns a pseudo-random integer in the range [0, UCHAR_MAX]. */ +unsigned char +prng_get_byte (void) +{ + unsigned byte; + int bits; + + byte = prng_get_octet (); + for (bits = 8; bits < CHAR_BIT; bits += 8) + byte = (byte << 8) | prng_get_octet (); + return byte; +} + +/* Fills BUF with SIZE pseudo-random bytes. */ +void +prng_get_bytes (void *buf_, size_t size) +{ + unsigned char *buf; + + for (buf = buf_; size-- > 0; buf++) + *buf = prng_get_byte (); +} + +/* Returns a pseudo-random unsigned long in the range [0, + ULONG_MAX]. */ +unsigned long +prng_get_ulong (void) +{ + unsigned long ulng; + size_t bits; + + ulng = prng_get_octet (); + for (bits = 8; bits < CHAR_BIT * sizeof ulng; bits += 8) + ulng = (ulng << 8) | prng_get_octet (); + return ulng; +} + +/* Returns a pseudo-random long in the range [0, LONG_MAX]. */ +long +prng_get_long (void) +{ + return prng_get_ulong () & LONG_MAX; +} + +/* Returns a pseudo-random unsigned int in the range [0, + UINT_MAX]. */ +unsigned +prng_get_uint (void) +{ + unsigned uint; + size_t bits; + + uint = prng_get_octet (); + for (bits = 8; bits < CHAR_BIT * sizeof uint; bits += 8) + uint = (uint << 8) | prng_get_octet (); + return uint; +} + +/* Returns a pseudo-random int in the range [0, INT_MAX]. */ +int +prng_get_int (void) +{ + return prng_get_uint () & INT_MAX; +} + +/* Returns a pseudo-random floating-point number from the uniform + distribution with range [0,1). */ +double +prng_get_double (void) +{ + for (;;) + { + double dbl = prng_get_ulong () / (ULONG_MAX + 1.0); + if (dbl >= 0.0 && dbl < 1.0) + return dbl; + } +} + +/* Returns a pseudo-random floating-point number from the + distribution with mean 0 and standard deviation 1. (Multiply + the result by the desired standard deviation, then add the + desired mean.) */ +double +prng_get_double_normal (void) +{ + /* Knuth, _The Art of Computer Programming_, Vol. 2, 3.4.1C, + Algorithm P. */ + static int has_next = 0; + static double next_normal; + double this_normal; + + if (has_next) + { + this_normal = next_normal; + has_next = 0; + } + else + { + static double limit; + double v1, v2, s; + + if (limit == 0.0) + limit = log (DBL_MAX / 2) / (DBL_MAX / 2); + + for (;;) + { + double u1 = prng_get_double (); + double u2 = prng_get_double (); + v1 = 2.0 * u1 - 1.0; + v2 = 2.0 * u2 - 1.0; + s = v1 * v1 + v2 * v2; + if (s > limit && s < 1) + break; + } + + this_normal = v1 * sqrt (-2. * log (s) / s); + next_normal = v2 * sqrt (-2. * log (s) / s); + has_next = 1; + } + + return this_normal; +}