-/***********************************************************
-* Artsoft Retro-Game Library *
-*----------------------------------------------------------*
-* (c) 1994-2002 Artsoft Entertainment *
-* Holger Schemel *
-* Detmolder Strasse 189 *
-* 33604 Bielefeld *
-* Germany *
-* e-mail: info@artsoft.org *
-*----------------------------------------------------------*
-* random.c *
-***********************************************************/
+// ============================================================================
+// 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.
#include <limits.h>
#include <stdlib.h>
-#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
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,
+ -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,
+};
+static int randtbl_1[DEG_3 + 1] =
{
TYPE_3,
-851904987, -43806228, -2029755270, 1390239686, -1912102820,
-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
cycle through the state information. (Yes, this does mean we could get
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] };
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.
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);
}
}
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 <blp@cs.stanford.edu>.
+ * 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 <assert.h>
+#include <float.h>
+#include <limits.h>
+#include <math.h>
+#include <time.h>
+
+/* 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;
+}