X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=glib%2Fgrand.c;h=6262cd21b79332354d9b99e236a72d9a22104913;hb=d217429729aad360f372633f2ec99778c0fc08d5;hp=83b1bc34e217f0cb0d6fb6ee90970fcfb9f064ec;hpb=f80d6cc540d1116f5e04f7ea20a54ecf12ea37a6;p=platform%2Fupstream%2Fglib.git diff --git a/glib/grand.c b/glib/grand.c index 83b1bc3..6262cd2 100644 --- a/glib/grand.c +++ b/glib/grand.c @@ -2,46 +2,121 @@ * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald * * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Library General Public + * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Library General Public License for more details. + * Lesser General Public License for more details. * - * You should have received a copy of the GNU Library General Public - * License along with this library; if not, write to the - * Free Software Foundation, Inc., 59 Temple Place - Suite 330, - * Boston, MA 02111-1307, USA. + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, see . */ /* Originally developed and coded by Makoto Matsumoto and Takuji * Nishimura. Please mail , if you're using * code from this file in your own programs or libraries. * Further information on the Mersenne Twister can be found at - * http://www.math.keio.ac.jp/~matumoto/emt.html - * This code was adapted to glib by Sebastian Wilhelmi . + * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html + * This code was adapted to glib by Sebastian Wilhelmi. */ /* - * Modified by the GLib Team and others 1997-1999. See the AUTHORS + * Modified by the GLib Team and others 1997-2000. See the AUTHORS * file for a list of people on the GLib Team. See the ChangeLog * files for a list of changes. These files are distributed with - * GLib at ftp://ftp.gtk.org/pub/gtk/. + * GLib at ftp://ftp.gtk.org/pub/gtk/. */ -/* +/* * MT safe */ -#include +#include "config.h" +#define _CRT_RAND_S + #include +#include #include +#include +#include +#include "grand.h" + +#include "genviron.h" +#include "gmain.h" +#include "gmem.h" +#include "gtestutils.h" +#include "gthread.h" + +#ifdef G_OS_UNIX +#include +#endif + +#ifdef G_OS_WIN32 +#include +#endif + +/** + * SECTION:random_numbers + * @title: Random Numbers + * @short_description: pseudo-random number generator + * + * The following functions allow you to use a portable, fast and good + * pseudo-random number generator (PRNG). + * + * Do not use this API for cryptographic purposes such as key + * generation, nonces, salts or one-time pads. + * + * This PRNG is suitable for non-cryptographic use such as in games + * (shuffling a card deck, generating levels), generating data for + * a test suite, etc. If you need random data for cryptographic + * purposes, it is recommended to use platform-specific APIs such + * as `/dev/random` on UNIX, or CryptGenRandom() on Windows. + * + * GRand uses the Mersenne Twister PRNG, which was originally + * developed by Makoto Matsumoto and Takuji Nishimura. Further + * information can be found at + * [this page](http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html). + * + * If you just need a random number, you simply call the g_random_* + * functions, which will create a globally used #GRand and use the + * according g_rand_* functions internally. Whenever you need a + * stream of reproducible random numbers, you better create a + * #GRand yourself and use the g_rand_* functions directly, which + * will also be slightly faster. Initializing a #GRand with a + * certain seed will produce exactly the same series of random + * numbers on all platforms. This can thus be used as a seed for + * e.g. games. + * + * The g_rand*_range functions will return high quality equally + * distributed random numbers, whereas for example the + * `(g_random_int()%max)` approach often + * doesn't yield equally distributed numbers. + * + * GLib changed the seeding algorithm for the pseudo-random number + * generator Mersenne Twister, as used by #GRand. This was necessary, + * because some seeds would yield very bad pseudo-random streams. + * Also the pseudo-random integers generated by g_rand*_int_range() + * will have a slightly better equal distribution with the new + * version of GLib. + * + * The original seeding and generation algorithms, as found in + * GLib 2.0.x, can be used instead of the new ones by setting the + * environment variable `G_RANDOM_VERSION` to the value of '2.0'. + * Use the GLib-2.0 algorithms only if you have sequences of numbers + * generated with Glib-2.0 that you need to reproduce exactly. + */ + +/** + * GRand: + * + * The GRand struct is an opaque data structure. It should only be + * accessed through the g_rand_* functions. + **/ G_LOCK_DEFINE_STATIC (global_random); -static GRand* global_random = NULL; /* Period parameters */ #define N 624 @@ -58,12 +133,46 @@ static GRand* global_random = NULL; #define TEMPERING_SHIFT_T(y) (y << 15) #define TEMPERING_SHIFT_L(y) (y >> 18) +static guint +get_random_version (void) +{ + static gsize initialized = FALSE; + static guint random_version; + + if (g_once_init_enter (&initialized)) + { + const gchar *version_string = g_getenv ("G_RANDOM_VERSION"); + if (!version_string || version_string[0] == '\000' || + strcmp (version_string, "2.2") == 0) + random_version = 22; + else if (strcmp (version_string, "2.0") == 0) + random_version = 20; + else + { + g_warning ("Unknown G_RANDOM_VERSION \"%s\". Using version 2.2.", + version_string); + random_version = 22; + } + g_once_init_leave (&initialized, TRUE); + } + + return random_version; +} + struct _GRand { guint32 mt[N]; /* the array for the state vector */ guint mti; }; +/** + * g_rand_new_with_seed: + * @seed: a value to initialize the random number generator + * + * Creates a new random number generator initialized with @seed. + * + * Returns: the new #GRand + **/ GRand* g_rand_new_with_seed (guint32 seed) { @@ -72,62 +181,258 @@ g_rand_new_with_seed (guint32 seed) return rand; } +/** + * g_rand_new_with_seed_array: + * @seed: an array of seeds to initialize the random number generator + * @seed_length: an array of seeds to initialize the random number + * generator + * + * Creates a new random number generator initialized with @seed. + * + * Returns: the new #GRand + * + * Since: 2.4 + */ +GRand* +g_rand_new_with_seed_array (const guint32 *seed, + guint seed_length) +{ + GRand *rand = g_new0 (GRand, 1); + g_rand_set_seed_array (rand, seed, seed_length); + return rand; +} + +/** + * g_rand_new: + * + * Creates a new random number generator initialized with a seed taken + * either from `/dev/urandom` (if existing) or from the current time + * (as a fallback). + * + * On Windows, the seed is taken from rand_s(). + * + * Returns: the new #GRand + */ GRand* g_rand_new (void) { - guint32 seed = 0; + guint32 seed[4]; +#ifdef G_OS_UNIX + static gboolean dev_urandom_exists = TRUE; GTimeVal now; - static gboolean dev_random_exists = TRUE; - - if (dev_random_exists) + + if (dev_urandom_exists) { - FILE* dev_random = fopen("/dev/random", "rb"); - if (dev_random) + FILE* dev_urandom; + + do { - if (fread (&seed, sizeof (seed), 1, dev_random) != 1) - seed = 0; - else - dev_random_exists = FALSE; - fclose (dev_random); + dev_urandom = fopen("/dev/urandom", "rb"); + } + while G_UNLIKELY (dev_urandom == NULL && errno == EINTR); + + if (dev_urandom) + { + int r; + + setvbuf (dev_urandom, NULL, _IONBF, 0); + do + { + errno = 0; + r = fread (seed, sizeof (seed), 1, dev_urandom); + } + while G_UNLIKELY (errno == EINTR); + + if (r != 1) + dev_urandom_exists = FALSE; + + fclose (dev_urandom); } else - dev_random_exists = FALSE; + dev_urandom_exists = FALSE; } - /* Using /dev/random alone makes the seed computable for the - outside. This might pose security problems somewhere. This should - yield better values */ + if (!dev_urandom_exists) + { + g_get_current_time (&now); + seed[0] = now.tv_sec; + seed[1] = now.tv_usec; + seed[2] = getpid (); + seed[3] = getppid (); + } +#else /* G_OS_WIN32 */ + gint i; - g_get_current_time (&now); - seed ^= now.tv_sec ^ now.tv_usec; + for (i = 0; i < G_N_ELEMENTS (seed); i++) + rand_s (&seed[i]); +#endif - return g_rand_new_with_seed (seed); + return g_rand_new_with_seed_array (seed, 4); } +/** + * g_rand_free: + * @rand_: a #GRand + * + * Frees the memory allocated for the #GRand. + */ void -g_rand_free (GRand* rand) +g_rand_free (GRand *rand) { g_return_if_fail (rand != NULL); g_free (rand); } +/** + * g_rand_copy: + * @rand_: a #GRand + * + * Copies a #GRand into a new one with the same exact state as before. + * This way you can take a snapshot of the random number generator for + * replaying later. + * + * Returns: the new #GRand + * + * Since: 2.4 + */ +GRand* +g_rand_copy (GRand *rand) +{ + GRand* new_rand; + + g_return_val_if_fail (rand != NULL, NULL); + + new_rand = g_new0 (GRand, 1); + memcpy (new_rand, rand, sizeof (GRand)); + + return new_rand; +} + +/** + * g_rand_set_seed: + * @rand_: a #GRand + * @seed: a value to reinitialize the random number generator + * + * Sets the seed for the random number generator #GRand to @seed. + */ +void +g_rand_set_seed (GRand *rand, + guint32 seed) +{ + g_return_if_fail (rand != NULL); + + switch (get_random_version ()) + { + case 20: + /* setting initial seeds to mt[N] using */ + /* the generator Line 25 of Table 1 in */ + /* [KNUTH 1981, The Art of Computer Programming */ + /* Vol. 2 (2nd Ed.), pp102] */ + + if (seed == 0) /* This would make the PRNG produce only zeros */ + seed = 0x6b842128; /* Just set it to another number */ + + rand->mt[0]= seed; + for (rand->mti=1; rand->mtimti++) + rand->mt[rand->mti] = (69069 * rand->mt[rand->mti-1]); + + break; + case 22: + /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */ + /* In the previous version (see above), MSBs of the */ + /* seed affect only MSBs of the array mt[]. */ + + rand->mt[0]= seed; + for (rand->mti=1; rand->mtimti++) + rand->mt[rand->mti] = 1812433253UL * + (rand->mt[rand->mti-1] ^ (rand->mt[rand->mti-1] >> 30)) + rand->mti; + break; + default: + g_assert_not_reached (); + } +} + +/** + * g_rand_set_seed_array: + * @rand_: a #GRand + * @seed: array to initialize with + * @seed_length: length of array + * + * Initializes the random number generator by an array of longs. + * Array can be of arbitrary size, though only the first 624 values + * are taken. This function is useful if you have many low entropy + * seeds, or if you require more then 32 bits of actual entropy for + * your application. + * + * Since: 2.4 + */ void -g_rand_set_seed (GRand* rand, guint32 seed) +g_rand_set_seed_array (GRand *rand, + const guint32 *seed, + guint seed_length) { + int i, j, k; + g_return_if_fail (rand != NULL); + g_return_if_fail (seed_length >= 1); + + g_rand_set_seed (rand, 19650218UL); + + i=1; j=0; + k = (N>seed_length ? N : seed_length); + for (; k; k--) + { + rand->mt[i] = (rand->mt[i] ^ + ((rand->mt[i-1] ^ (rand->mt[i-1] >> 30)) * 1664525UL)) + + seed[j] + j; /* non linear */ + rand->mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */ + i++; j++; + if (i>=N) + { + rand->mt[0] = rand->mt[N-1]; + i=1; + } + if (j>=seed_length) + j=0; + } + for (k=N-1; k; k--) + { + rand->mt[i] = (rand->mt[i] ^ + ((rand->mt[i-1] ^ (rand->mt[i-1] >> 30)) * 1566083941UL)) + - i; /* non linear */ + rand->mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */ + i++; + if (i>=N) + { + rand->mt[0] = rand->mt[N-1]; + i=1; + } + } - /* setting initial seeds to mt[N] using */ - /* the generator Line 25 of Table 1 in */ - /* [KNUTH 1981, The Art of Computer Programming */ - /* Vol. 2 (2nd Ed.), pp102] */ - rand->mt[0]= seed & 0xffffffff; - for (rand->mti=1; rand->mtimti++) - rand->mt[rand->mti] = (69069 * rand->mt[rand->mti-1]) & 0xffffffff; + rand->mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */ } +/** + * g_rand_boolean: + * @rand_: a #GRand + * + * Returns a random #gboolean from @rand_. + * This corresponds to a unbiased coin toss. + * + * Returns: a random #gboolean + */ +/** + * g_rand_int: + * @rand_: a #GRand + * + * Returns the next random #guint32 from @rand_ equally distributed over + * the range [0..2^32-1]. + * + * Returns: a random number + */ guint32 -g_rand_int (GRand* rand) +g_rand_int (GRand *rand) { guint32 y; static const guint32 mag01[2]={0x0, MATRIX_A}; @@ -138,11 +443,11 @@ g_rand_int (GRand* rand) if (rand->mti >= N) { /* generate N words at one time */ int kk; - for (kk=0;kkmt[kk]&UPPER_MASK)|(rand->mt[kk+1]&LOWER_MASK); rand->mt[kk] = rand->mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1]; } - for (;kkmt[kk]&UPPER_MASK)|(rand->mt[kk+1]&LOWER_MASK); rand->mt[kk] = rand->mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1]; } @@ -161,132 +466,250 @@ g_rand_int (GRand* rand) return y; } +/* transform [0..2^32] -> [0..1] */ +#define G_RAND_DOUBLE_TRANSFORM 2.3283064365386962890625e-10 + +/** + * g_rand_int_range: + * @rand_: a #GRand + * @begin: lower closed bound of the interval + * @end: upper open bound of the interval + * + * Returns the next random #gint32 from @rand_ equally distributed over + * the range [@begin..@end-1]. + * + * Returns: a random number + */ gint32 -g_rand_int_range (GRand* rand, gint32 min, gint32 max) +g_rand_int_range (GRand *rand, + gint32 begin, + gint32 end) { - guint32 dist = max - min; + guint32 dist = end - begin; guint32 random; - g_return_val_if_fail (rand != NULL, min); - g_return_val_if_fail (max > min, min); + g_return_val_if_fail (rand != NULL, begin); + g_return_val_if_fail (end > begin, begin); - if (dist <= 0x10000L) /* 2^16 */ + switch (get_random_version ()) { - /* All tricks doing modulo calculations do not have a good - distribution -> We must use this slower method for maximal - quality, but this method is only good for (max - min) <= 2^16 */ - - random = (gint32) g_rand_double_range (rand, 0, dist); - /* we'd rather use the following, if -lm is allowed later on: - random = (gint32) floor (g_rand_double_range (rand, 0, dist)); */ - } - else - { - /* Now it's harder to make it right. We calculate the smallest m, - such that dist < 2 ^ m, then we calculate a random number in - [1..2^32-1] and rightshift it by 32 - m. Then we test, if it - is smaller than dist and if not, get a new number and so - forth until we get a number smaller than dist. We just return - this. */ - guint32 border = 0x20000L; /* 2^17 */ - guint right_shift = 15; /* 32 - 17 */ - - if (dist >= 0x80000000) /* in the case of dist > 2^31 our loop - below will be infinite */ + case 20: + if (dist <= 0x10000L) /* 2^16 */ { - right_shift = 0; + /* This method, which only calls g_rand_int once is only good + * for (end - begin) <= 2^16, because we only have 32 bits set + * from the one call to g_rand_int (). + * + * We are using (trans + trans * trans), because g_rand_int only + * covers [0..2^32-1] and thus g_rand_int * trans only covers + * [0..1-2^-32], but the biggest double < 1 is 1-2^-52. + */ + + gdouble double_rand = g_rand_int (rand) * + (G_RAND_DOUBLE_TRANSFORM + + G_RAND_DOUBLE_TRANSFORM * G_RAND_DOUBLE_TRANSFORM); + + random = (gint32) (double_rand * dist); } else { - while (dist >= border) + /* Now we use g_rand_double_range (), which will set 52 bits + * for us, so that it is safe to round and still get a decent + * distribution + */ + random = (gint32) g_rand_double_range (rand, 0, dist); + } + break; + case 22: + if (dist == 0) + random = 0; + else + { + /* maxvalue is set to the predecessor of the greatest + * multiple of dist less or equal 2^32. + */ + guint32 maxvalue; + if (dist <= 0x80000000u) /* 2^31 */ { - border <<= 1; - right_shift--; + /* maxvalue = 2^32 - 1 - (2^32 % dist) */ + guint32 leftover = (0x80000000u % dist) * 2; + if (leftover >= dist) leftover -= dist; + maxvalue = 0xffffffffu - leftover; } + else + maxvalue = dist - 1; + + do + random = g_rand_int (rand); + while (random > maxvalue); + + random %= dist; } - do - { - random = g_rand_int (rand) >> right_shift; - } while (random >= dist); - } - return min + random; + break; + default: + random = 0; /* Quiet GCC */ + g_assert_not_reached (); + } + + return begin + random; } -/* transform [0..2^32-1] -> [0..1) */ -#define G_RAND_DOUBLE_TRANSFORM 2.3283064365386963e-10 - +/** + * g_rand_double: + * @rand_: a #GRand + * + * Returns the next random #gdouble from @rand_ equally distributed over + * the range [0..1). + * + * Returns: a random number + */ gdouble -g_rand_double (GRand* rand) -{ - return g_rand_int (rand) * G_RAND_DOUBLE_TRANSFORM; +g_rand_double (GRand *rand) +{ + /* We set all 52 bits after the point for this, not only the first + 32. Thats why we need two calls to g_rand_int */ + gdouble retval = g_rand_int (rand) * G_RAND_DOUBLE_TRANSFORM; + retval = (retval + g_rand_int (rand)) * G_RAND_DOUBLE_TRANSFORM; + + /* The following might happen due to very bad rounding luck, but + * actually this should be more than rare, we just try again then */ + if (retval >= 1.0) + return g_rand_double (rand); + + return retval; } +/** + * g_rand_double_range: + * @rand_: a #GRand + * @begin: lower closed bound of the interval + * @end: upper open bound of the interval + * + * Returns the next random #gdouble from @rand_ equally distributed over + * the range [@begin..@end). + * + * Returns: a random number + */ gdouble -g_rand_double_range (GRand* rand, gdouble min, gdouble max) +g_rand_double_range (GRand *rand, + gdouble begin, + gdouble end) +{ + gdouble r; + + r = g_rand_double (rand); + + return r * end - (r - 1) * begin; +} + +static GRand * +get_global_random (void) { - return g_rand_int (rand) * ((max - min) * G_RAND_DOUBLE_TRANSFORM) + min; + static GRand *global_random; + + /* called while locked */ + if (!global_random) + global_random = g_rand_new (); + + return global_random; } +/** + * g_random_boolean: + * + * Returns a random #gboolean. + * This corresponds to a unbiased coin toss. + * + * Returns: a random #gboolean + */ +/** + * g_random_int: + * + * Return a random #guint32 equally distributed over the range + * [0..2^32-1]. + * + * Returns: a random number + */ guint32 g_random_int (void) { guint32 result; G_LOCK (global_random); - if (!global_random) - global_random = g_rand_new (); - - result = g_rand_int (global_random); + result = g_rand_int (get_global_random ()); G_UNLOCK (global_random); return result; } +/** + * g_random_int_range: + * @begin: lower closed bound of the interval + * @end: upper open bound of the interval + * + * Returns a random #gint32 equally distributed over the range + * [@begin..@end-1]. + * + * Returns: a random number + */ gint32 -g_random_int_range (gint32 min, gint32 max) +g_random_int_range (gint32 begin, + gint32 end) { gint32 result; G_LOCK (global_random); - if (!global_random) - global_random = g_rand_new (); - - result = g_rand_int_range (global_random, min, max); + result = g_rand_int_range (get_global_random (), begin, end); G_UNLOCK (global_random); return result; } +/** + * g_random_double: + * + * Returns a random #gdouble equally distributed over the range [0..1). + * + * Returns: a random number + */ gdouble g_random_double (void) { double result; G_LOCK (global_random); - if (!global_random) - global_random = g_rand_new (); - - result = g_rand_double (global_random); + result = g_rand_double (get_global_random ()); G_UNLOCK (global_random); return result; } +/** + * g_random_double_range: + * @begin: lower closed bound of the interval + * @end: upper open bound of the interval + * + * Returns a random #gdouble equally distributed over the range + * [@begin..@end). + * + * Returns: a random number + */ gdouble -g_random_double_range (gdouble min, gdouble max) +g_random_double_range (gdouble begin, + gdouble end) { double result; G_LOCK (global_random); - if (!global_random) - global_random = g_rand_new (); - - result = g_rand_double_range (global_random, min, max); + result = g_rand_double_range (get_global_random (), begin, end); G_UNLOCK (global_random); return result; } +/** + * g_random_set_seed: + * @seed: a value to reinitialize the global random number generator + * + * Sets the seed for the global random number generator, which is used + * by the g_random_* functions, to @seed. + */ void g_random_set_seed (guint32 seed) { G_LOCK (global_random); - if (!global_random) - global_random = g_rand_new_with_seed (seed); - else - g_rand_set_seed (global_random, seed); + g_rand_set_seed (get_global_random (), seed); G_UNLOCK (global_random); } -