-/***********************************************************
-* 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_0[DEG_3 + 1] =
+static int randtbl_0[DEG_3 + 1] =
{
TYPE_3,
-851904987, -43806228, -2029755270, 1390239686, -1912102820,
-607508183, -205999574, -1696891592, 1492211999, -1528267240,
-952028296, -189082757, 362343714, 1424981831, 2039449641,
};
-static long int randtbl_1[DEG_3 + 1] =
+static int randtbl_1[DEG_3 + 1] =
{
TYPE_3,
-851904987, -43806228, -2029755270, 1390239686, -1912102820,
in the initialization of randtbl) because the state table pointer is set
to point to randtbl[1] (as explained below).) */
-static long int *fptr[2] = { &randtbl_0[SEP_3 + 1], &randtbl_1[SEP_3 + 1] };
-static long int *rptr[2] = { &randtbl_0[1], &randtbl_1[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[2] = { &randtbl_0[1], &randtbl_1[1] };
+static int *state[2] = { &randtbl_0[1], &randtbl_1[1] };
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[2] =
+static int *end_ptr[2] =
{
&randtbl_0[sizeof(randtbl_0) / sizeof(randtbl_0[0])],
&randtbl_1[sizeof(randtbl_1) / sizeof(randtbl_1[0])]
if (rand_type[nr] != TYPE_0)
{
- register long int i;
+ register int i;
for (i = 1; i < rand_deg[nr]; ++i)
state[nr][i] = (1103515145 * state[nr][i - 1]) + 12345;
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 nr)
+int random_linux_libc(int nr)
{
if (rand_type[nr] == TYPE_0)
{
- state[nr][0] = ((state[nr][0] * 1103515245) + 12345) & LONG_MAX;
+ state[nr][0] = ((state[nr][0] * 1103515245) + 12345) & INT_MAX;
return state[nr][0];
}
else
{
- long int i;
+ int i;
*fptr[nr] += *rptr[nr];
/* Chucking least random bit. */
- i = (*fptr[nr] >> 1) & LONG_MAX;
+ i = (*fptr[nr] >> 1) & INT_MAX;
fptr[nr]++;
if (fptr[nr] >= end_ptr[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;
+}