From 08e04cf7570d270bb5a8284f79a605237f648b3d Mon Sep 17 00:00:00 2001 From: Holger Schemel Date: Wed, 5 Jan 2022 12:42:33 +0100 Subject: [PATCH] added improved pseudo-random number generator --- src/libgame/random.c | 276 ++++++++++++++++++++++++++++++++++++++++++- src/libgame/random.h | 17 +++ 2 files changed, 291 insertions(+), 2 deletions(-) diff --git a/src/libgame/random.c b/src/libgame/random.c index 7877d82d..fd409d06 100644 --- a/src/libgame/random.c +++ b/src/libgame/random.c @@ -9,6 +9,9 @@ // random.c // ============================================================================ +#include "random.h" + + /* * Copyright (c) 1983 Regents of the University of California. * All rights reserved. @@ -36,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 @@ -257,3 +258,274 @@ int random_linux_libc(int 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; +} diff --git a/src/libgame/random.h b/src/libgame/random.h index 63a54c37..0da74da4 100644 --- a/src/libgame/random.h +++ b/src/libgame/random.h @@ -15,4 +15,21 @@ void srandom_linux_libc(int, unsigned int); int random_linux_libc(int); + +// ============================================================================ + +#include + +void prng_seed_time (void); +void prng_seed_bytes (const void *, size_t); +unsigned char prng_get_octet (void); +unsigned char prng_get_byte (void); +void prng_get_bytes (void *, size_t); +unsigned long prng_get_ulong (void); +long prng_get_long (void); +unsigned prng_get_uint (void); +int prng_get_int (void); +double prng_get_double (void); +double prng_get_double_normal (void); + #endif -- 2.34.1