1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
18 /* Originally developed and coded by Makoto Matsumoto and Takuji
19 * Nishimura. Please mail <matumoto@math.keio.ac.jp>, if you're using
20 * code from this file in your own programs or libraries.
21 * Further information on the Mersenne Twister can be found at
22 * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
23 * This code was adapted to glib by Sebastian Wilhelmi.
27 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
28 * file for a list of people on the GLib Team. See the ChangeLog
29 * files for a list of changes. These files are distributed with
30 * GLib at ftp://ftp.gtk.org/pub/gtk/.
44 #include <sys/types.h>
50 #include "gtestutils.h"
59 #include <process.h> /* For getpid() */
63 * SECTION:random_numbers
64 * @title: Random Numbers
65 * @short_description: pseudo-random number generator
67 * The following functions allow you to use a portable, fast and good
68 * pseudo-random number generator (PRNG).
70 * Do not use this API for cryptographic purposes such as key
71 * generation, nonces, salts or one-time pads.
73 * This PRNG is suitable for non-cryptographic use such as in games
74 * (shuffling a card deck, generating levels), generating data for
75 * a test suite, etc. If you need random data for cryptographic
76 * purposes, it is recommended to use platform-specific APIs such
77 * as `/dev/random` on UNIX, or CryptGenRandom() on Windows.
79 * GRand uses the Mersenne Twister PRNG, which was originally
80 * developed by Makoto Matsumoto and Takuji Nishimura. Further
81 * information can be found at
82 * [this page](http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html).
84 * If you just need a random number, you simply call the g_random_*
85 * functions, which will create a globally used #GRand and use the
86 * according g_rand_* functions internally. Whenever you need a
87 * stream of reproducible random numbers, you better create a
88 * #GRand yourself and use the g_rand_* functions directly, which
89 * will also be slightly faster. Initializing a #GRand with a
90 * certain seed will produce exactly the same series of random
91 * numbers on all platforms. This can thus be used as a seed for
94 * The g_rand*_range functions will return high quality equally
95 * distributed random numbers, whereas for example the
96 * `(g_random_int()%max)` approach often
97 * doesn't yield equally distributed numbers.
99 * GLib changed the seeding algorithm for the pseudo-random number
100 * generator Mersenne Twister, as used by #GRand. This was necessary,
101 * because some seeds would yield very bad pseudo-random streams.
102 * Also the pseudo-random integers generated by g_rand*_int_range()
103 * will have a slightly better equal distribution with the new
106 * The original seeding and generation algorithms, as found in
107 * GLib 2.0.x, can be used instead of the new ones by setting the
108 * environment variable `G_RANDOM_VERSION` to the value of '2.0'.
109 * Use the GLib-2.0 algorithms only if you have sequences of numbers
110 * generated with Glib-2.0 that you need to reproduce exactly.
116 * The GRand struct is an opaque data structure. It should only be
117 * accessed through the g_rand_* functions.
120 G_LOCK_DEFINE_STATIC (global_random
);
122 /* Period parameters */
125 #define MATRIX_A 0x9908b0df /* constant vector a */
126 #define UPPER_MASK 0x80000000 /* most significant w-r bits */
127 #define LOWER_MASK 0x7fffffff /* least significant r bits */
129 /* Tempering parameters */
130 #define TEMPERING_MASK_B 0x9d2c5680
131 #define TEMPERING_MASK_C 0xefc60000
132 #define TEMPERING_SHIFT_U(y) (y >> 11)
133 #define TEMPERING_SHIFT_S(y) (y << 7)
134 #define TEMPERING_SHIFT_T(y) (y << 15)
135 #define TEMPERING_SHIFT_L(y) (y >> 18)
138 get_random_version (void)
140 static gsize initialized
= FALSE
;
141 static guint random_version
;
143 if (g_once_init_enter (&initialized
))
145 const gchar
*version_string
= g_getenv ("G_RANDOM_VERSION");
146 if (!version_string
|| version_string
[0] == '\000' ||
147 strcmp (version_string
, "2.2") == 0)
149 else if (strcmp (version_string
, "2.0") == 0)
153 g_warning ("Unknown G_RANDOM_VERSION \"%s\". Using version 2.2.",
157 g_once_init_leave (&initialized
, TRUE
);
160 return random_version
;
165 guint32 mt
[N
]; /* the array for the state vector */
170 * g_rand_new_with_seed:
171 * @seed: a value to initialize the random number generator
173 * Creates a new random number generator initialized with @seed.
175 * Returns: the new #GRand
178 g_rand_new_with_seed (guint32 seed
)
180 GRand
*rand
= g_new0 (GRand
, 1);
181 g_rand_set_seed (rand
, seed
);
186 * g_rand_new_with_seed_array:
187 * @seed: an array of seeds to initialize the random number generator
188 * @seed_length: an array of seeds to initialize the random number
191 * Creates a new random number generator initialized with @seed.
193 * Returns: the new #GRand
198 g_rand_new_with_seed_array (const guint32
*seed
,
201 GRand
*rand
= g_new0 (GRand
, 1);
202 g_rand_set_seed_array (rand
, seed
, seed_length
);
209 * Creates a new random number generator initialized with a seed taken
210 * either from `/dev/urandom` (if existing) or from the current time
213 * On Windows, the seed is taken from rand_s().
215 * Returns: the new #GRand
222 static gboolean dev_urandom_exists
= TRUE
;
225 if (dev_urandom_exists
)
231 dev_urandom
= fopen("/dev/urandom", "rb");
233 while G_UNLIKELY (dev_urandom
== NULL
&& errno
== EINTR
);
239 setvbuf (dev_urandom
, NULL
, _IONBF
, 0);
243 r
= fread (seed
, sizeof (seed
), 1, dev_urandom
);
245 while G_UNLIKELY (errno
== EINTR
);
248 dev_urandom_exists
= FALSE
;
250 fclose (dev_urandom
);
253 dev_urandom_exists
= FALSE
;
256 if (!dev_urandom_exists
)
258 g_get_current_time (&now
);
259 seed
[0] = now
.tv_sec
;
260 seed
[1] = now
.tv_usec
;
262 seed
[3] = getppid ();
264 #else /* G_OS_WIN32 */
265 /* rand_s() is only available since Visual Studio 2005 */
266 #if defined(_MSC_VER) && _MSC_VER >= 1400
269 for (i
= 0; i
< G_N_ELEMENTS (seed
); i
++)
272 #warning Using insecure seed for random number generation because of missing rand_s() in Windows XP
275 g_get_current_time (&now
);
276 seed
[0] = now
.tv_sec
;
277 seed
[1] = now
.tv_usec
;
284 return g_rand_new_with_seed_array (seed
, 4);
291 * Frees the memory allocated for the #GRand.
294 g_rand_free (GRand
*rand
)
296 g_return_if_fail (rand
!= NULL
);
305 * Copies a #GRand into a new one with the same exact state as before.
306 * This way you can take a snapshot of the random number generator for
309 * Returns: the new #GRand
314 g_rand_copy (GRand
*rand
)
318 g_return_val_if_fail (rand
!= NULL
, NULL
);
320 new_rand
= g_new0 (GRand
, 1);
321 memcpy (new_rand
, rand
, sizeof (GRand
));
329 * @seed: a value to reinitialize the random number generator
331 * Sets the seed for the random number generator #GRand to @seed.
334 g_rand_set_seed (GRand
*rand
,
337 g_return_if_fail (rand
!= NULL
);
339 switch (get_random_version ())
342 /* setting initial seeds to mt[N] using */
343 /* the generator Line 25 of Table 1 in */
344 /* [KNUTH 1981, The Art of Computer Programming */
345 /* Vol. 2 (2nd Ed.), pp102] */
347 if (seed
== 0) /* This would make the PRNG produce only zeros */
348 seed
= 0x6b842128; /* Just set it to another number */
351 for (rand
->mti
=1; rand
->mti
<N
; rand
->mti
++)
352 rand
->mt
[rand
->mti
] = (69069 * rand
->mt
[rand
->mti
-1]);
356 /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
357 /* In the previous version (see above), MSBs of the */
358 /* seed affect only MSBs of the array mt[]. */
361 for (rand
->mti
=1; rand
->mti
<N
; rand
->mti
++)
362 rand
->mt
[rand
->mti
] = 1812433253UL *
363 (rand
->mt
[rand
->mti
-1] ^ (rand
->mt
[rand
->mti
-1] >> 30)) + rand
->mti
;
366 g_assert_not_reached ();
371 * g_rand_set_seed_array:
373 * @seed: array to initialize with
374 * @seed_length: length of array
376 * Initializes the random number generator by an array of longs.
377 * Array can be of arbitrary size, though only the first 624 values
378 * are taken. This function is useful if you have many low entropy
379 * seeds, or if you require more then 32 bits of actual entropy for
385 g_rand_set_seed_array (GRand
*rand
,
391 g_return_if_fail (rand
!= NULL
);
392 g_return_if_fail (seed_length
>= 1);
394 g_rand_set_seed (rand
, 19650218UL);
397 k
= (N
>seed_length
? N
: seed_length
);
400 rand
->mt
[i
] = (rand
->mt
[i
] ^
401 ((rand
->mt
[i
-1] ^ (rand
->mt
[i
-1] >> 30)) * 1664525UL))
402 + seed
[j
] + j
; /* non linear */
403 rand
->mt
[i
] &= 0xffffffffUL
; /* for WORDSIZE > 32 machines */
407 rand
->mt
[0] = rand
->mt
[N
-1];
415 rand
->mt
[i
] = (rand
->mt
[i
] ^
416 ((rand
->mt
[i
-1] ^ (rand
->mt
[i
-1] >> 30)) * 1566083941UL))
417 - i
; /* non linear */
418 rand
->mt
[i
] &= 0xffffffffUL
; /* for WORDSIZE > 32 machines */
422 rand
->mt
[0] = rand
->mt
[N
-1];
427 rand
->mt
[0] = 0x80000000UL
; /* MSB is 1; assuring non-zero initial array */
434 * Returns a random #gboolean from @rand_.
435 * This corresponds to a unbiased coin toss.
437 * Returns: a random #gboolean
443 * Returns the next random #guint32 from @rand_ equally distributed over
444 * the range [0..2^32-1].
446 * Returns: a random number
449 g_rand_int (GRand
*rand
)
452 static const guint32 mag01
[2]={0x0, MATRIX_A
};
453 /* mag01[x] = x * MATRIX_A for x=0,1 */
455 g_return_val_if_fail (rand
!= NULL
, 0);
457 if (rand
->mti
>= N
) { /* generate N words at one time */
460 for (kk
= 0; kk
< N
- M
; kk
++) {
461 y
= (rand
->mt
[kk
]&UPPER_MASK
)|(rand
->mt
[kk
+1]&LOWER_MASK
);
462 rand
->mt
[kk
] = rand
->mt
[kk
+M
] ^ (y
>> 1) ^ mag01
[y
& 0x1];
464 for (; kk
< N
- 1; kk
++) {
465 y
= (rand
->mt
[kk
]&UPPER_MASK
)|(rand
->mt
[kk
+1]&LOWER_MASK
);
466 rand
->mt
[kk
] = rand
->mt
[kk
+(M
-N
)] ^ (y
>> 1) ^ mag01
[y
& 0x1];
468 y
= (rand
->mt
[N
-1]&UPPER_MASK
)|(rand
->mt
[0]&LOWER_MASK
);
469 rand
->mt
[N
-1] = rand
->mt
[M
-1] ^ (y
>> 1) ^ mag01
[y
& 0x1];
474 y
= rand
->mt
[rand
->mti
++];
475 y
^= TEMPERING_SHIFT_U(y
);
476 y
^= TEMPERING_SHIFT_S(y
) & TEMPERING_MASK_B
;
477 y
^= TEMPERING_SHIFT_T(y
) & TEMPERING_MASK_C
;
478 y
^= TEMPERING_SHIFT_L(y
);
483 /* transform [0..2^32] -> [0..1] */
484 #define G_RAND_DOUBLE_TRANSFORM 2.3283064365386962890625e-10
489 * @begin: lower closed bound of the interval
490 * @end: upper open bound of the interval
492 * Returns the next random #gint32 from @rand_ equally distributed over
493 * the range [@begin..@end-1].
495 * Returns: a random number
498 g_rand_int_range (GRand
*rand
,
502 guint32 dist
= end
- begin
;
505 g_return_val_if_fail (rand
!= NULL
, begin
);
506 g_return_val_if_fail (end
> begin
, begin
);
508 switch (get_random_version ())
511 if (dist
<= 0x10000L
) /* 2^16 */
513 /* This method, which only calls g_rand_int once is only good
514 * for (end - begin) <= 2^16, because we only have 32 bits set
515 * from the one call to g_rand_int ().
517 * We are using (trans + trans * trans), because g_rand_int only
518 * covers [0..2^32-1] and thus g_rand_int * trans only covers
519 * [0..1-2^-32], but the biggest double < 1 is 1-2^-52.
522 gdouble double_rand
= g_rand_int (rand
) *
523 (G_RAND_DOUBLE_TRANSFORM
+
524 G_RAND_DOUBLE_TRANSFORM
* G_RAND_DOUBLE_TRANSFORM
);
526 random
= (gint32
) (double_rand
* dist
);
530 /* Now we use g_rand_double_range (), which will set 52 bits
531 * for us, so that it is safe to round and still get a decent
534 random
= (gint32
) g_rand_double_range (rand
, 0, dist
);
542 /* maxvalue is set to the predecessor of the greatest
543 * multiple of dist less or equal 2^32.
546 if (dist
<= 0x80000000u
) /* 2^31 */
548 /* maxvalue = 2^32 - 1 - (2^32 % dist) */
549 guint32 leftover
= (0x80000000u
% dist
) * 2;
550 if (leftover
>= dist
) leftover
-= dist
;
551 maxvalue
= 0xffffffffu
- leftover
;
557 random
= g_rand_int (rand
);
558 while (random
> maxvalue
);
564 random
= 0; /* Quiet GCC */
565 g_assert_not_reached ();
568 return begin
+ random
;
575 * Returns the next random #gdouble from @rand_ equally distributed over
578 * Returns: a random number
581 g_rand_double (GRand
*rand
)
583 /* We set all 52 bits after the point for this, not only the first
584 32. Thats why we need two calls to g_rand_int */
585 gdouble retval
= g_rand_int (rand
) * G_RAND_DOUBLE_TRANSFORM
;
586 retval
= (retval
+ g_rand_int (rand
)) * G_RAND_DOUBLE_TRANSFORM
;
588 /* The following might happen due to very bad rounding luck, but
589 * actually this should be more than rare, we just try again then */
591 return g_rand_double (rand
);
597 * g_rand_double_range:
599 * @begin: lower closed bound of the interval
600 * @end: upper open bound of the interval
602 * Returns the next random #gdouble from @rand_ equally distributed over
603 * the range [@begin..@end).
605 * Returns: a random number
608 g_rand_double_range (GRand
*rand
,
614 r
= g_rand_double (rand
);
616 return r
* end
- (r
- 1) * begin
;
620 get_global_random (void)
622 static GRand
*global_random
;
624 /* called while locked */
626 global_random
= g_rand_new ();
628 return global_random
;
634 * Returns a random #gboolean.
635 * This corresponds to a unbiased coin toss.
637 * Returns: a random #gboolean
642 * Return a random #guint32 equally distributed over the range
645 * Returns: a random number
651 G_LOCK (global_random
);
652 result
= g_rand_int (get_global_random ());
653 G_UNLOCK (global_random
);
658 * g_random_int_range:
659 * @begin: lower closed bound of the interval
660 * @end: upper open bound of the interval
662 * Returns a random #gint32 equally distributed over the range
665 * Returns: a random number
668 g_random_int_range (gint32 begin
,
672 G_LOCK (global_random
);
673 result
= g_rand_int_range (get_global_random (), begin
, end
);
674 G_UNLOCK (global_random
);
681 * Returns a random #gdouble equally distributed over the range [0..1).
683 * Returns: a random number
686 g_random_double (void)
689 G_LOCK (global_random
);
690 result
= g_rand_double (get_global_random ());
691 G_UNLOCK (global_random
);
696 * g_random_double_range:
697 * @begin: lower closed bound of the interval
698 * @end: upper open bound of the interval
700 * Returns a random #gdouble equally distributed over the range
703 * Returns: a random number
706 g_random_double_range (gdouble begin
,
710 G_LOCK (global_random
);
711 result
= g_rand_double_range (get_global_random (), begin
, end
);
712 G_UNLOCK (global_random
);
718 * @seed: a value to reinitialize the global random number generator
720 * Sets the seed for the global random number generator, which is used
721 * by the g_random_* functions, to @seed.
724 g_random_set_seed (guint32 seed
)
726 G_LOCK (global_random
);
727 g_rand_set_seed (get_global_random (), seed
);
728 G_UNLOCK (global_random
);