X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=glib%2Fgrand.c;h=4c0e0b4e9d299b3d9ffbb4255e50b517535ecb9e;hb=45f221c32f7c88e487fe260eefb3be8d1c2443af;hp=39741a82001e171684150f053d903a3098bdaabd;hpb=3fa33317b7e9866793ce1ea32d069e8c9270caa2;p=platform%2Fupstream%2Fglib.git diff --git a/glib/grand.c b/glib/grand.c index 39741a8..4c0e0b4 100644 --- a/glib/grand.c +++ b/glib/grand.c @@ -21,24 +21,94 @@ * 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-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" + #include +#include #include +#include +#include +#ifdef HAVE_UNISTD_H +#include +#endif + +#include "grand.h" + +#include "genviron.h" +#include "gmain.h" +#include "gmem.h" +#include "gtestutils.h" +#include "gthread.h" +#include "gthreadprivate.h" + +#ifdef G_OS_WIN32 +#include /* For getpid() */ +#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). It uses the Mersenne Twister + * PRNG, which was originally developed by Makoto Matsumoto and Takuji + * Nishimura. Further information can be found at + * + * 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 and GRandom. + * 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; @@ -58,6 +128,32 @@ 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 */ @@ -81,6 +177,25 @@ g_rand_new_with_seed (guint32 seed) } /** + * 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. + * + * Return value: 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 @@ -92,18 +207,37 @@ g_rand_new_with_seed (guint32 seed) GRand* g_rand_new (void) { - guint32 seed; + guint32 seed[4]; GTimeVal now; #ifdef G_OS_UNIX static gboolean dev_urandom_exists = TRUE; if (dev_urandom_exists) { - FILE* dev_urandom = fopen("/dev/urandom", "rb"); + FILE* dev_urandom; + + do + { + errno = 0; + dev_urandom = fopen("/dev/urandom", "rb"); + } + while G_UNLIKELY (errno == EINTR); + if (dev_urandom) { - if (fread (&seed, sizeof (seed), 1, dev_urandom) != 1) + 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 @@ -116,15 +250,22 @@ g_rand_new (void) if (!dev_urandom_exists) { g_get_current_time (&now); - seed = now.tv_sec ^ now.tv_usec; + seed[0] = now.tv_sec; + seed[1] = now.tv_usec; + seed[2] = getpid (); +#ifdef G_OS_UNIX + seed[3] = getppid (); +#else + seed[3] = 0; +#endif } - return g_rand_new_with_seed (seed); + return g_rand_new_with_seed_array (seed, 4); } /** * g_rand_free: - * @rand: a #GRand. + * @rand_: a #GRand. * * Frees the memory allocated for the #GRand. **/ @@ -137,8 +278,33 @@ g_rand_free (GRand* 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. + * + * Return value: 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. + * @rand_: a #GRand. * @seed: a value to reinitialize the random number generator. * * Sets the seed for the random number generator #GRand to @seed. @@ -148,24 +314,108 @@ g_rand_set_seed (GRand* rand, guint32 seed) { g_return_if_fail (rand != NULL); - /* 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 procude only zeros */ - seed = 0x6b842128; /* Just set it to another number */ + 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 procude 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 (); + } +} - rand->mt[0]= seed & 0xffffffff; - for (rand->mti=1; rand->mtimti++) - rand->mt[rand->mti] = (69069 * rand->mt[rand->mti-1]) & 0xffffffff; +/** + * 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 + * 32bits of actual entropy for your application. + * + * Since: 2.4 + **/ +void +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; + } + } + + rand->mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */ } /** + * g_rand_boolean: + * @rand_: a #GRand. + * @Returns: a random #gboolean. + * + * Returns a random #gboolean from @rand_. This corresponds to a + * unbiased coin toss. + **/ +/** * g_rand_int: - * @rand: a #GRand. + * @rand_: a #GRand. * - * Returns the next random #guint32 from @rand equally distributed over + * Returns the next random #guint32 from @rand_ equally distributed over * the range [0..2^32-1]. * * Return value: A random number. @@ -210,11 +460,11 @@ g_rand_int (GRand* rand) /** * g_rand_int_range: - * @rand: a #GRand. + * @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 + * Returns the next random #gint32 from @rand_ equally distributed over * the range [@begin..@end-1]. * * Return value: A random number. @@ -228,43 +478,72 @@ g_rand_int_range (GRand* rand, gint32 begin, gint32 end) g_return_val_if_fail (rand != NULL, begin); g_return_val_if_fail (end > begin, begin); - /* All tricks doing modulo calculations do not have a perfect - * distribution -> We must use the slower way through gdouble for - * maximal quality. */ - - if (dist <= 0x10000L) /* 2^16 */ + switch (get_random_version ()) { - /* 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 - { - /* 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); - } + case 20: + if (dist <= 0x10000L) /* 2^16 */ + { + /* 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 + { + /* 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 */ + { + /* 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; + } + break; + default: + random = 0; /* Quiet GCC */ + g_assert_not_reached (); + } return begin + random; } /** * g_rand_double: - * @rand: a #GRand. + * @rand_: a #GRand. * - * Returns the next random #gdouble from @rand equally distributed over + * Returns the next random #gdouble from @rand_ equally distributed over * the range [0..1). * * Return value: A random number. @@ -287,11 +566,11 @@ g_rand_double (GRand* rand) /** * g_rand_double_range: - * @rand: a #GRand. + * @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 + * Returns the next random #gdouble from @rand_ equally distributed over * the range [@begin..@end). * * Return value: A random number. @@ -299,10 +578,20 @@ g_rand_double (GRand* rand) gdouble g_rand_double_range (GRand* rand, gdouble begin, gdouble end) { - return g_rand_double (rand) * (end - begin) + begin; + gdouble r; + + r = g_rand_double (rand); + + return r * end - (r - 1) * begin; } /** + * g_random_boolean: + * @Returns: a random #gboolean. + * + * Returns a random #gboolean. This corresponds to a unbiased coin toss. + **/ +/** * g_random_int: * * Return a random #guint32 equally distributed over the range @@ -405,4 +694,3 @@ g_random_set_seed (guint32 seed) g_rand_set_seed (global_random, seed); G_UNLOCK (global_random); } -