1/*
2 * $Id: mt19937db.c,v 12.9 2008/03/12 19:23:38 mbrey Exp $
3 */
4#include "db_config.h"
5
6#include "db_int.h"
7#include "dbinc/crypto.h"
8#include "dbinc/hmac.h"
9
10/* A C-program for MT19937: Integer version (1999/10/28)          */
11/*  genrand() generates one pseudorandom unsigned integer (32bit) */
12/* which is uniformly distributed among 0 to 2^32-1  for each     */
13/* call. sgenrand(seed) sets initial values to the working area   */
14/* of 624 words. Before genrand(), sgenrand(seed) must be         */
15/* called once. (seed is any 32-bit integer.)                     */
16/*   Coded by Takuji Nishimura, considering the suggestions by    */
17/* Topher Cooper and Marc Rieffel in July-Aug. 1997.              */
18
19/* This library is free software under the Artistic license:       */
20/* see the file COPYING distributed together with this code.       */
21/* For the verification of the code, its output sequence file      */
22/* mt19937int.out is attached (2001/4/2)                           */
23
24/* Copyright (C) 1997, 1999 Makoto Matsumoto and Takuji Nishimura. */
25/* Any feedback is very welcome. For any question, comments,       */
26/* see http://www.math.keio.ac.jp/matumoto/emt.html or email       */
27/* matumoto@math.keio.ac.jp                                        */
28
29/* REFERENCE                                                       */
30/* M. Matsumoto and T. Nishimura,                                  */
31/* "Mersenne Twister: A 623-Dimensionally Equidistributed Uniform  */
32/* Pseudo-Random Number Generator",                                */
33/* ACM Transactions on Modeling and Computer Simulation,           */
34/* Vol. 8, No. 1, January 1998, pp 3--30.                          */
35
36/* Period parameters */
37#define	N 624
38#define	M 397
39#define	MATRIX_A 0x9908b0df   /* constant vector a */
40#define	UPPER_MASK 0x80000000 /* most significant w-r bits */
41#define	LOWER_MASK 0x7fffffff /* least significant r bits */
42
43/* Tempering parameters */
44#define	TEMPERING_MASK_B 0x9d2c5680
45#define	TEMPERING_MASK_C 0xefc60000
46#define	TEMPERING_SHIFT_U(y)  (y >> 11)
47#define	TEMPERING_SHIFT_S(y)  (y << 7)
48#define	TEMPERING_SHIFT_T(y)  (y << 15)
49#define	TEMPERING_SHIFT_L(y)  (y >> 18)
50
51static void __db_sgenrand __P((unsigned long, unsigned long *, int *));
52#ifdef	NOT_USED
53static void __db_lsgenrand __P((unsigned long *, unsigned long *, int *));
54#endif
55static unsigned long __db_genrand __P((ENV *));
56
57/*
58 * __db_generate_iv --
59 *	Generate an initialization vector (IV)
60 *
61 * PUBLIC: int __db_generate_iv __P((ENV *, u_int32_t *));
62 */
63int
64__db_generate_iv(env, iv)
65	ENV *env;
66	u_int32_t *iv;
67{
68	int i, n, ret;
69
70	ret = 0;
71	n = DB_IV_BYTES / sizeof(u_int32_t);
72	MUTEX_LOCK(env, env->mtx_mt);
73	if (env->mt == NULL) {
74		if ((ret = __os_calloc(env, 1, N*sizeof(unsigned long),
75		    &env->mt)) != 0)
76			return (ret);
77		/* mti==N+1 means mt[N] is not initialized */
78		env->mti = N + 1;
79	}
80	for (i = 0; i < n; i++) {
81		/*
82		 * We do not allow 0.  If we get one just try again.
83		 */
84		do {
85			iv[i] = (u_int32_t)__db_genrand(env);
86		} while (iv[i] == 0);
87	}
88
89	MUTEX_UNLOCK(env, env->mtx_mt);
90	return (0);
91}
92
93/* Initializing the array with a seed */
94static void
95__db_sgenrand(seed, mt, mtip)
96	unsigned long seed;
97	unsigned long mt[];
98	int *mtip;
99{
100    int i;
101
102    DB_ASSERT(NULL, seed != 0);
103    for (i=0;i<N;i++) {
104	 mt[i] = seed & 0xffff0000;
105	 seed = 69069 * seed + 1;
106	 mt[i] |= (seed & 0xffff0000) >> 16;
107	 seed = 69069 * seed + 1;
108    }
109    *mtip = N;
110}
111
112#ifdef	NOT_USED
113/* Initialization by "sgenrand()" is an example. Theoretically,      */
114/* there are 2^19937-1 possible states as an intial state.           */
115/* This function allows to choose any of 2^19937-1 ones.             */
116/* Essential bits in "seed_array[]" is following 19937 bits:         */
117/*  (seed_array[0]&UPPER_MASK), seed_array[1], ..., seed_array[N-1]. */
118/* (seed_array[0]&LOWER_MASK) is discarded.                          */
119/* Theoretically,                                                    */
120/*  (seed_array[0]&UPPER_MASK), seed_array[1], ..., seed_array[N-1]  */
121/* can take any values except all zeros.                             */
122static void
123__db_lsgenrand(seed_array, mt, mtip)
124    unsigned long seed_array[];
125    unsigned long mt[];
126    int *mtip;
127    /* the length of seed_array[] must be at least N */
128{
129    int i;
130
131    for (i=0;i<N;i++)
132      mt[i] = seed_array[i];
133    *mtip=N;
134}
135#endif
136
137static unsigned long
138__db_genrand(env)
139    ENV *env;
140{
141    db_timespec ts;
142    unsigned long y;
143    static unsigned long mag01[2]={0x0, MATRIX_A};
144    /* mag01[x] = x * MATRIX_A  for x=0,1 */
145    u_int32_t seed;
146
147    /*
148     * We are called with ENV->mtx_mt locked.
149     */
150    if (env->mti >= N) { /* generate N words at one time */
151	int kk;
152
153	if (env->mti == N+1) {  /* if sgenrand() has not been called, */
154		/*
155		 * Seed the generator with the hashed time.  The __db_mac
156		 * function will return 4 bytes if we don't send in a key.
157		 */
158		do {
159			__os_gettime(env, &ts, 1);
160			__db_chksum(NULL, (u_int8_t *)&ts.tv_sec,
161			    sizeof(ts.tv_sec), NULL, (u_int8_t *)&seed);
162		} while (seed == 0);
163		__db_sgenrand((unsigned long)seed, env->mt, &env->mti);
164	}
165
166	for (kk=0;kk<N-M;kk++) {
167	    y = (env->mt[kk]&UPPER_MASK)|(env->mt[kk+1]&LOWER_MASK);
168	    env->mt[kk] = env->mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1];
169	}
170	for (;kk<N-1;kk++) {
171	    y = (env->mt[kk]&UPPER_MASK)|(env->mt[kk+1]&LOWER_MASK);
172	    env->mt[kk] = env->mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1];
173	}
174	y = (env->mt[N-1]&UPPER_MASK)|(env->mt[0]&LOWER_MASK);
175	env->mt[N-1] = env->mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1];
176
177	env->mti = 0;
178    }
179
180    y = env->mt[env->mti++];
181    y ^= TEMPERING_SHIFT_U(y);
182    y ^= TEMPERING_SHIFT_S(y) & TEMPERING_MASK_B;
183    y ^= TEMPERING_SHIFT_T(y) & TEMPERING_MASK_C;
184    y ^= TEMPERING_SHIFT_L(y);
185
186    return y;
187}
188