From c838b2a0712ee0a6595821839bf528467936ab0e Mon Sep 17 00:00:00 2001 From: Sebastian Wilhelmi Date: Tue, 26 Nov 2002 14:09:00 +0000 Subject: [PATCH] Improved the seeding algorithm. Old behaviour can be achived by setting 2002-11-26 Sebastian Wilhelmi * glib/grand.c, gthread/gthread-impl.c, tests/rand-test.c: Improved the seeding algorithm. Old behaviour can be achived by setting envvar G_RANDOM_VERSION to "2.0". (#99262) * docs/reference/glib/glib-docs.sgml, docs/reference/glib/Makefile.am: Renamed docs/reference/glib/changes-2.0.sgml to docs/reference/glib/changes.sgml and added section for changes from 2.0 to 2.2 (Also corrected 1.0 to 1.2). * README.in, docs/reference/glib/running.sgml, docs/reference/glib/tmpl/random_numbers.sgml, docs/reference/glib/changes.sgml: Added notes about the new seeding algorithm. --- ChangeLog | 17 ++++- ChangeLog.pre-2-10 | 17 ++++- ChangeLog.pre-2-12 | 17 ++++- ChangeLog.pre-2-2 | 17 ++++- ChangeLog.pre-2-4 | 17 ++++- ChangeLog.pre-2-6 | 17 ++++- ChangeLog.pre-2-8 | 17 ++++- README.in | 16 +++++ docs/reference/glib/Makefile.am | 2 +- .../glib/{changes-2.0.sgml => changes.sgml} | 46 +++++++++++-- docs/reference/glib/glib-docs.sgml | 4 +- docs/reference/glib/running.sgml | 11 ++++ docs/reference/glib/tmpl/random_numbers.sgml | 16 ++++- glib/grand.c | 75 ++++++++++++++++++---- gthread/gthread-impl.c | 2 + tests/rand-test.c | 40 ++++++------ 16 files changed, 281 insertions(+), 50 deletions(-) rename docs/reference/glib/{changes-2.0.sgml => changes.sgml} (71%) diff --git a/ChangeLog b/ChangeLog index b517599..1505da8 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,9 +1,24 @@ 2002-11-26 Sebastian Wilhelmi + * glib/grand.c, gthread/gthread-impl.c, tests/rand-test.c: + Changed the seeding algorithm. Old behaviour can be achived by + setting envvar G_RANDOM_VERSION to "2.0". (#99262) + + * docs/reference/glib/glib-docs.sgml, + docs/reference/glib/Makefile.am: Renamed + docs/reference/glib/changes-2.0.sgml to + docs/reference/glib/changes.sgml and added section for changes + from 2.0 to 2.2 (Also corrected 1.0 to 1.2). + + * README.in, docs/reference/glib/running.sgml, + docs/reference/glib/tmpl/random_numbers.sgml, + docs/reference/glib/changes.sgml: Added notes about the new + seeding algorithm. + * configure.in: Make CPPFLAGS, not CFLAGS, include G_THREAD_CFLAGS. CFLAGS is used while linking too and thus GLib programs would link to the threads library on some platforms. Also - fixed a bug manifesting through this change. + fixed a bug manifesting through this change. (#77981) 2002-11-26 Matthias Clasen diff --git a/ChangeLog.pre-2-10 b/ChangeLog.pre-2-10 index b517599..1505da8 100644 --- a/ChangeLog.pre-2-10 +++ b/ChangeLog.pre-2-10 @@ -1,9 +1,24 @@ 2002-11-26 Sebastian Wilhelmi + * glib/grand.c, gthread/gthread-impl.c, tests/rand-test.c: + Changed the seeding algorithm. Old behaviour can be achived by + setting envvar G_RANDOM_VERSION to "2.0". (#99262) + + * docs/reference/glib/glib-docs.sgml, + docs/reference/glib/Makefile.am: Renamed + docs/reference/glib/changes-2.0.sgml to + docs/reference/glib/changes.sgml and added section for changes + from 2.0 to 2.2 (Also corrected 1.0 to 1.2). + + * README.in, docs/reference/glib/running.sgml, + docs/reference/glib/tmpl/random_numbers.sgml, + docs/reference/glib/changes.sgml: Added notes about the new + seeding algorithm. + * configure.in: Make CPPFLAGS, not CFLAGS, include G_THREAD_CFLAGS. CFLAGS is used while linking too and thus GLib programs would link to the threads library on some platforms. Also - fixed a bug manifesting through this change. + fixed a bug manifesting through this change. (#77981) 2002-11-26 Matthias Clasen diff --git a/ChangeLog.pre-2-12 b/ChangeLog.pre-2-12 index b517599..1505da8 100644 --- a/ChangeLog.pre-2-12 +++ b/ChangeLog.pre-2-12 @@ -1,9 +1,24 @@ 2002-11-26 Sebastian Wilhelmi + * glib/grand.c, gthread/gthread-impl.c, tests/rand-test.c: + Changed the seeding algorithm. Old behaviour can be achived by + setting envvar G_RANDOM_VERSION to "2.0". (#99262) + + * docs/reference/glib/glib-docs.sgml, + docs/reference/glib/Makefile.am: Renamed + docs/reference/glib/changes-2.0.sgml to + docs/reference/glib/changes.sgml and added section for changes + from 2.0 to 2.2 (Also corrected 1.0 to 1.2). + + * README.in, docs/reference/glib/running.sgml, + docs/reference/glib/tmpl/random_numbers.sgml, + docs/reference/glib/changes.sgml: Added notes about the new + seeding algorithm. + * configure.in: Make CPPFLAGS, not CFLAGS, include G_THREAD_CFLAGS. CFLAGS is used while linking too and thus GLib programs would link to the threads library on some platforms. Also - fixed a bug manifesting through this change. + fixed a bug manifesting through this change. (#77981) 2002-11-26 Matthias Clasen diff --git a/ChangeLog.pre-2-2 b/ChangeLog.pre-2-2 index b517599..1505da8 100644 --- a/ChangeLog.pre-2-2 +++ b/ChangeLog.pre-2-2 @@ -1,9 +1,24 @@ 2002-11-26 Sebastian Wilhelmi + * glib/grand.c, gthread/gthread-impl.c, tests/rand-test.c: + Changed the seeding algorithm. Old behaviour can be achived by + setting envvar G_RANDOM_VERSION to "2.0". (#99262) + + * docs/reference/glib/glib-docs.sgml, + docs/reference/glib/Makefile.am: Renamed + docs/reference/glib/changes-2.0.sgml to + docs/reference/glib/changes.sgml and added section for changes + from 2.0 to 2.2 (Also corrected 1.0 to 1.2). + + * README.in, docs/reference/glib/running.sgml, + docs/reference/glib/tmpl/random_numbers.sgml, + docs/reference/glib/changes.sgml: Added notes about the new + seeding algorithm. + * configure.in: Make CPPFLAGS, not CFLAGS, include G_THREAD_CFLAGS. CFLAGS is used while linking too and thus GLib programs would link to the threads library on some platforms. Also - fixed a bug manifesting through this change. + fixed a bug manifesting through this change. (#77981) 2002-11-26 Matthias Clasen diff --git a/ChangeLog.pre-2-4 b/ChangeLog.pre-2-4 index b517599..1505da8 100644 --- a/ChangeLog.pre-2-4 +++ b/ChangeLog.pre-2-4 @@ -1,9 +1,24 @@ 2002-11-26 Sebastian Wilhelmi + * glib/grand.c, gthread/gthread-impl.c, tests/rand-test.c: + Changed the seeding algorithm. Old behaviour can be achived by + setting envvar G_RANDOM_VERSION to "2.0". (#99262) + + * docs/reference/glib/glib-docs.sgml, + docs/reference/glib/Makefile.am: Renamed + docs/reference/glib/changes-2.0.sgml to + docs/reference/glib/changes.sgml and added section for changes + from 2.0 to 2.2 (Also corrected 1.0 to 1.2). + + * README.in, docs/reference/glib/running.sgml, + docs/reference/glib/tmpl/random_numbers.sgml, + docs/reference/glib/changes.sgml: Added notes about the new + seeding algorithm. + * configure.in: Make CPPFLAGS, not CFLAGS, include G_THREAD_CFLAGS. CFLAGS is used while linking too and thus GLib programs would link to the threads library on some platforms. Also - fixed a bug manifesting through this change. + fixed a bug manifesting through this change. (#77981) 2002-11-26 Matthias Clasen diff --git a/ChangeLog.pre-2-6 b/ChangeLog.pre-2-6 index b517599..1505da8 100644 --- a/ChangeLog.pre-2-6 +++ b/ChangeLog.pre-2-6 @@ -1,9 +1,24 @@ 2002-11-26 Sebastian Wilhelmi + * glib/grand.c, gthread/gthread-impl.c, tests/rand-test.c: + Changed the seeding algorithm. Old behaviour can be achived by + setting envvar G_RANDOM_VERSION to "2.0". (#99262) + + * docs/reference/glib/glib-docs.sgml, + docs/reference/glib/Makefile.am: Renamed + docs/reference/glib/changes-2.0.sgml to + docs/reference/glib/changes.sgml and added section for changes + from 2.0 to 2.2 (Also corrected 1.0 to 1.2). + + * README.in, docs/reference/glib/running.sgml, + docs/reference/glib/tmpl/random_numbers.sgml, + docs/reference/glib/changes.sgml: Added notes about the new + seeding algorithm. + * configure.in: Make CPPFLAGS, not CFLAGS, include G_THREAD_CFLAGS. CFLAGS is used while linking too and thus GLib programs would link to the threads library on some platforms. Also - fixed a bug manifesting through this change. + fixed a bug manifesting through this change. (#77981) 2002-11-26 Matthias Clasen diff --git a/ChangeLog.pre-2-8 b/ChangeLog.pre-2-8 index b517599..1505da8 100644 --- a/ChangeLog.pre-2-8 +++ b/ChangeLog.pre-2-8 @@ -1,9 +1,24 @@ 2002-11-26 Sebastian Wilhelmi + * glib/grand.c, gthread/gthread-impl.c, tests/rand-test.c: + Changed the seeding algorithm. Old behaviour can be achived by + setting envvar G_RANDOM_VERSION to "2.0". (#99262) + + * docs/reference/glib/glib-docs.sgml, + docs/reference/glib/Makefile.am: Renamed + docs/reference/glib/changes-2.0.sgml to + docs/reference/glib/changes.sgml and added section for changes + from 2.0 to 2.2 (Also corrected 1.0 to 1.2). + + * README.in, docs/reference/glib/running.sgml, + docs/reference/glib/tmpl/random_numbers.sgml, + docs/reference/glib/changes.sgml: Added notes about the new + seeding algorithm. + * configure.in: Make CPPFLAGS, not CFLAGS, include G_THREAD_CFLAGS. CFLAGS is used while linking too and thus GLib programs would link to the threads library on some platforms. Also - fixed a bug manifesting through this change. + fixed a bug manifesting through this change. (#77981) 2002-11-26 Matthias Clasen diff --git a/README.in b/README.in index a78a9d7..856bab4 100644 --- a/README.in +++ b/README.in @@ -24,6 +24,22 @@ Installation See the file 'INSTALL' +Notes about GLib-2.2.0 +====================== + +* 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. Further information can be found at: + + http://www.math.keio.ac.jp/~matumoto/emt.html + + The original seeding algorithm, as found in GLib-2.0.x, can be used + instead of the new one by setting the environment variable + G_RANDOM_VERSION to the value of "2.0". Use the GLib-2.0 algorithm + only if you have sequences of numbers generated with Glib-2.0 that + you need to reproduce exactly. + How to report bugs ================== diff --git a/docs/reference/glib/Makefile.am b/docs/reference/glib/Makefile.am index 3dda474..5a8d436 100644 --- a/docs/reference/glib/Makefile.am +++ b/docs/reference/glib/Makefile.am @@ -48,7 +48,7 @@ HTML_IMAGES = \ content_files = \ running.sgml \ building.sgml \ - changes-2.0.sgml \ + changes.sgml \ compiling.sgml \ resources.sgml \ version.xml diff --git a/docs/reference/glib/changes-2.0.sgml b/docs/reference/glib/changes.sgml similarity index 71% rename from docs/reference/glib/changes-2.0.sgml rename to docs/reference/glib/changes.sgml index 7a6d2ff..ae8f503 100644 --- a/docs/reference/glib/changes-2.0.sgml +++ b/docs/reference/glib/changes.sgml @@ -1,26 +1,58 @@ - + -Changes from 1.0 to 2.0 +Changes to GLib 3 -Changes from 1.0 to 2.0 +Changes to GLib -Changes from 1.0 to 2.0 +Changes to GLib -Incompatible changes made between version 1.0 and version 2.0 +Incompatible changes made between successing versions of GLib -Incompatible changes from 1.0 to 2.0 +Incompatible changes from 2.0 to 2.2 + + + + + +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. + + + +Further information can be found at the website of the Mersenne +Twister random number generator at http://www.math.keio.ac.jp/~matumoto/emt.html. + + + +The original seeding algorithm, as found in GLib 2.0.x, can be used +instead of the new one by setting the environment variable +G_RANDOM_VERSION to the value of '2.0'. Use the +GLib-2.0 algorithm only if you have sequences of numbers generated +with Glib-2.0 that you need to reproduce exactly. + + + + + + + + +Incompatible changes from 1.2 to 2.0 The GNOME 2.0 porting guide on http://developer.gnome.org -has some more detailed discussion of porting from 1.0 to 2.0. +has some more detailed discussion of porting from 1.2 to 2.0. See the section on GLib. diff --git a/docs/reference/glib/glib-docs.sgml b/docs/reference/glib/glib-docs.sgml index 5a37681..a0147f5 100644 --- a/docs/reference/glib/glib-docs.sgml +++ b/docs/reference/glib/glib-docs.sgml @@ -58,7 +58,7 @@ - + ]> @@ -107,7 +107,7 @@ implementations, e.g. POSIX threads, DCE threads or Solaris threads. &glib-Building; &glib-Compiling; &glib-Running; - &glib-Changes-2-0; + &glib-Changes; &glib-Resources; diff --git a/docs/reference/glib/running.sgml b/docs/reference/glib/running.sgml index 94d5512..b933883 100644 --- a/docs/reference/glib/running.sgml +++ b/docs/reference/glib/running.sgml @@ -62,6 +62,17 @@ variables like LANG, PATH or HOME. + + <envar>G_RANDOM_VERSION</envar> + + + If this environment variable is set to '2.0', the outdated + pseudo-random number seeding algorithm from GLib-2.0 is used + instead of the new better one. Use the GLib-2.0 algorithm only if + you have sequences of numbers generated with Glib-2.0 that you + need to reproduce exactly. + + diff --git a/docs/reference/glib/tmpl/random_numbers.sgml b/docs/reference/glib/tmpl/random_numbers.sgml index ada8a85..9ff4ee5 100644 --- a/docs/reference/glib/tmpl/random_numbers.sgml +++ b/docs/reference/glib/tmpl/random_numbers.sgml @@ -2,12 +2,12 @@ Random Numbers -pseudo random number generator. +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 +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 + +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. The original seeding +algorithm, as found in GLib 2.0.x, can be used instead of the new one +by setting the environment variable G_RANDOM_VERSION to +the value of '2.0'. Use the GLib-2.0 algorithm only if you have +sequences of numbers generated with Glib-2.0 that you need to +reproduce exactly. + + diff --git a/glib/grand.c b/glib/grand.c index 58f2107..36d53ff 100644 --- a/glib/grand.c +++ b/glib/grand.c @@ -58,6 +58,41 @@ 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 gboolean initialized = FALSE; + static guint random_version; + + if (!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; + } + initialized = TRUE; + } + + return random_version; +} + +/* This is called from g_thread_init(). It's used to + * initialize some static data in a threadsafe way. + */ +void +g_rand_init (void) +{ + (void)get_random_version (); +} + struct _GRand { guint32 mt[N]; /* the array for the state vector */ @@ -148,17 +183,35 @@ 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 */ - - rand->mt[0]= seed & 0xffffffff; - for (rand->mti=1; rand->mtimti++) - rand->mt[rand->mti] = (69069 * rand->mt[rand->mti-1]) & 0xffffffff; + 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 (); + } } /** diff --git a/gthread/gthread-impl.c b/gthread/gthread-impl.c index 28d97e0..bed7050 100644 --- a/gthread/gthread-impl.c +++ b/gthread/gthread-impl.c @@ -66,6 +66,7 @@ void g_mutex_init (void); void g_mem_init (void); void g_messages_init (void); void g_convert_init (void); +void g_rand_init (void); void g_main_thread_init (void); #define G_MUTEX_DEBUG_INFO(mutex) (*((gpointer*)(((char*)mutex)+G_MUTEX_SIZE))) @@ -382,6 +383,7 @@ g_thread_init (GThreadFunctions* init) g_mem_init (); g_messages_init (); g_convert_init (); + g_rand_init (); g_main_thread_init (); /* now we can set g_threads_got_initialized and thus enable diff --git a/tests/rand-test.c b/tests/rand-test.c index 014c4da..c8efa21 100644 --- a/tests/rand-test.c +++ b/tests/rand-test.c @@ -6,26 +6,26 @@ const gint32 first_numbers[] = { 0x7a7a7a7a, - 0x20aea82a, - 0xcab337ab, - 0xdcf770ea, - 0xdf552b2f, - 0x32d1ef7f, - 0x6bed6dd9, - 0x7222df44, - 0x6b842128, - 0x07f8579a, - 0x9dad1004, - 0x2df264f2, - 0x13b48989, - 0xf2929475, - 0x30f30c97, - 0x3f9a1ea7, - 0x3bf04710, - 0xb85bd69e, - 0x790a48b0, - 0xfa06b85f, - 0xa64cc9e3 + 0xfdcc2d54, + 0x3a279ceb, + 0xc4d39c33, + 0xf31895cd, + 0x46ca0afc, + 0x3f5484ff, + 0x54bc9557, + 0xed2c24b1, + 0x84062503, + 0x8f6404b3, + 0x599a94b3, + 0xe46d03d5, + 0x310beb78, + 0x7bee5d08, + 0x760d09be, + 0x59b6e163, + 0xbf6d16ec, + 0xcca5fb54, + 0x5de7259b, + 0x1696330c, }; const gint length = sizeof (first_numbers) / sizeof (first_numbers[0]); -- 2.7.4