GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: src/air/randMT.c Lines: 60 66 90.9 %
Date: 2017-05-26 Branches: 19 26 73.1 %

Line Branch Exec Source
1
/*
2
  Teem: Tools to process and visualize scientific data and images             .
3
  Copyright (C) 2013, 2012, 2011, 2010, 2009  University of Chicago
4
  Copyright (C) 2008, 2007, 2006, 2005  Gordon Kindlmann
5
  Copyright (C) 2004, 2003, 2002, 2001, 2000, 1999, 1998  University of Utah
6
7
  This library is free software; you can redistribute it and/or
8
  modify it under the terms of the GNU Lesser General Public License
9
  (LGPL) as published by the Free Software Foundation; either
10
  version 2.1 of the License, or (at your option) any later version.
11
  The terms of redistributing and/or modifying this software also
12
  include exceptions to the LGPL that facilitate static linking.
13
14
  This library is distributed in the hope that it will be useful,
15
  but WITHOUT ANY WARRANTY; without even the implied warranty of
16
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17
  Lesser General Public License for more details.
18
19
  You should have received a copy of the GNU Lesser General Public License
20
  along with this library; if not, write to Free Software Foundation, Inc.,
21
  51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
22
*/
23
/*
24
  This file is a modified version of the MersenneTwister.h source file
25
  written by Richard J. Wagner.  The original copyright notice follows.
26
27
  Mersenne Twister random number generator -- a C++ class MTRand
28
  Based on code by Makoto Matsumoto, Takuji Nishimura, and Shawn Cokus
29
  Richard J. Wagner  v1.0  15 May 2003  rjwagner@writeme.com
30
31
  The Mersenne Twister is an algorithm for generating random numbers.  It
32
  was designed with consideration of the flaws in various other generators.
33
  The period, 2^19937-1, and the order of equidistribution, 623 dimensions,
34
  are far greater.  The generator is also fast; it avoids multiplication and
35
  division, and it benefits from caches and pipelines.  For more information
36
  see the inventors' web page at http://www.math.keio.ac.jp/~matumoto/emt.html
37
38
  Reference
39
  M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally
40
  Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions on
41
  Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
42
43
  Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
44
  Copyright (C) 2000 - 2003, Richard J. Wagner
45
  All rights reserved.
46
47
  Redistribution and use in source and binary forms, with or without
48
  modification, are permitted provided that the following conditions
49
  are met:
50
51
  1. Redistributions of source code must retain the above copyright
52
  notice, this list of conditions and the following disclaimer.
53
54
  2. Redistributions in binary form must reproduce the above copyright
55
  notice, this list of conditions and the following disclaimer in the
56
  documentation and/or other materials provided with the distribution.
57
58
  3. The names of its contributors may not be used to endorse or promote
59
  products derived from this software without specific prior written
60
  permission.
61
62
  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
63
  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
64
  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
65
  FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
66
  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
67
  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
68
  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
69
  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
70
  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
71
  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
72
  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
73
  POSSIBILITY OF SUCH DAMAGE.
74
75
  The original code included the following notice:
76
77
  When you use this, send an email to: matumoto@math.keio.ac.jp
78
  with an appropriate reference to your work.
79
80
  It would be nice to CC: rjwagner@writeme.com and Cokus@math.washington.edu
81
  when you write.
82
*/
83
84
#include "air.h"
85
#include "privateAir.h"
86
87
#define AIR_RANDMT_M 397
88
#define AIR_RANDMT_DEFAULT_SEED 42
89
90
/* Inlined class member functions that I made macros */
91
#define HIBIT( u ) ((u) & 0x80000000UL)
92
#define LOBIT( u ) ((u) & 0x00000001UL)
93
#define LOBITS( u ) ((u) & 0x7fffffffUL)
94
#define MIXBITS( u, v ) (HIBIT(u) | LOBITS(v))
95
#define TWOSCOMP( u ) (~(u)+1)
96
#define TWIST( m, s0, s1 ) \
97
  ((m) ^ (MIXBITS(s0,s1)>>1) ^ (TWOSCOMP(LOBIT(s1)) & 0x9908b0dfUL))
98
99
/* airRandMTStateGlobal is not allocated at compile-time because of
100
   weirdness of where non-initialized global objects go in shared
101
   libraries.  Its allocation and initialization are controlled by
102
   _airRandMTStateGlobal_{allocated,initialized}. Users who want to
103
   ensure thread safety should be using airRandMTStateNew and
104
   airDrandMT_r, not the global state.
105
*/
106
107
airRandMTState *airRandMTStateGlobal = NULL;
108
static int _airRandMTStateGlobal_allocated = AIR_FALSE;
109
static int _airRandMTStateGlobal_initialized = AIR_FALSE;
110
111
static void
112
_airRandMTInitialize(airRandMTState *rng, unsigned int seed) {
113
  /* Initialize generator state with seed See Knuth TAOCP Vol 2, 3rd
114
   Ed, p.106 for multiplier.  In previous versions, most significant
115
   bits (MSBs) of the seed affect only MSBs of the state array.
116
   Modified 9 Jan 2002 by Makoto Matsumoto.
117
  */
118
186
  register unsigned int *s = rng->state;
119
  register unsigned int *r = rng->state;
120
  register int i = 1;
121
93
  *s++ = seed & 0xffffffffUL;
122
116064
  for( ; i < AIR_RANDMT_N; ++i ) {
123
57939
    *s++ = ( 1812433253UL * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffUL;
124
57939
    r++;
125
  }
126
93
}
127
128
static void
129
_airRandMTReload(airRandMTState *rng) {
130
  /* Generate N new values in state.  Made clearer and faster by
131
     Matthew Bellew (matthew.bellew@home.com) */
132
  register int i;
133
65994
  register unsigned int *p = rng->state;
134
15046632
  for (i=AIR_RANDMT_N - AIR_RANDMT_M; i--; ++p) {
135
7490319
    *p = TWIST( p[AIR_RANDMT_M], p[0], p[1] );
136
  }
137

39299427
  for (i=AIR_RANDMT_M; --i; ++p) {
138
26166621
    *p = TWIST( p[AIR_RANDMT_M-AIR_RANDMT_N], p[0], p[1] );
139
  }
140
32997
  *p = TWIST( p[AIR_RANDMT_M-AIR_RANDMT_N], p[0], rng->state[0] );
141
142
32997
  rng->left = AIR_RANDMT_N;
143
32997
  rng->pNext = rng->state;
144
32997
}
145
146
airRandMTState *
147
airRandMTStateNew(unsigned int seed) {
148
  airRandMTState* ret;
149
150
128
  ret = AIR_CAST(airRandMTState*, malloc(sizeof(airRandMTState)));
151
64
  airSrandMT_r(ret, seed);
152
64
  return ret;
153
}
154
155
airRandMTState *
156
airRandMTStateNix(airRandMTState *state) {
157
104
  airFree(state);
158
52
  return NULL;
159
}
160
161
void
162
airSrandMT_r(airRandMTState *rng, unsigned int seed) {
163
  /* Seed the generator with a simple uint32 */
164
186
  _airRandMTInitialize(rng, seed);
165
93
  _airRandMTReload(rng);
166
93
}
167
168
/* Pull a 32-bit integer from the generator state.  Every other access
169
** function simply transforms the numbers extracted here.
170
*/
171
unsigned int
172
airUIrandMT_r(airRandMTState *rng) {
173
  register unsigned int s1;
174
175
41079958
  if (rng->left == 0) {
176
32904
    _airRandMTReload(rng);
177
32904
  }
178
20539979
  --rng->left;
179
180
20539979
  s1 = *rng->pNext++;
181
20539979
  s1 ^= (s1 >> 11);
182
20539979
  s1 ^= (s1 <<  7) & 0x9d2c5680UL;
183
20539979
  s1 ^= (s1 << 15) & 0xefc60000UL;
184
20539979
  return ( s1 ^ (s1 >> 18) );
185
}
186
187
/* This generates the closed interval [0,1] */
188
double
189
airDrandMT_r(airRandMTState *rng) {
190
28259248
  double result = airUIrandMT_r(rng);
191
14129624
  return result * (1.0/4294967295.0);
192
}
193
194
/* [0,1) w/ 53 bit precision (capacity of IEEE double precision) */
195
double
196
airDrandMT53_r(airRandMTState *rng) {
197
  unsigned int a, b;
198
  a = airUIrandMT_r(rng) >> 5;
199
  b = airUIrandMT_r(rng) >> 6;
200
  return ( a * 67108864.0 + b ) * (1.0/9007199254740992.0); /* by Isaku Wada */
201
}
202
203
#define _GLOBAL_ALLOC \
204
  if (!_airRandMTStateGlobal_allocated) { \
205
    airRandMTStateGlobal = airRandMTStateNew(0); \
206
    _airRandMTStateGlobal_allocated = AIR_TRUE; \
207
  }
208
#define _GLOBAL_INIT \
209
  if (!_airRandMTStateGlobal_initialized) { \
210
    airSrandMT(AIR_RANDMT_DEFAULT_SEED); \
211
  } \
212
213
/*
214
******** airRandMTStateGlobalInit
215
**
216
** Allocates and initializes airRandMTStateGlobal if it was not already
217
** allocated and initialized.  However, this does not need to be called
218
** except if the user wants to use the airRandMTStateGlobal pointer.
219
** The allocation and initialization is done as necessary inside the
220
** the airSrandMT(), airDrandMT(), etc functions (all the functions
221
** that use airRandMTStateGlobal
222
*/
223
void
224
airRandMTStateGlobalInit() {
225
  _GLOBAL_ALLOC;
226
  _GLOBAL_INIT;
227
}
228
229
void
230
airSrandMT(unsigned int seed) {
231
48
  _GLOBAL_ALLOC;
232
19
  airSrandMT_r(airRandMTStateGlobal, seed);
233
19
  _airRandMTStateGlobal_initialized = AIR_TRUE;
234
19
}
235
236
double
237
airDrandMT() {
238
28232396
  _GLOBAL_ALLOC;
239
14116198
  _GLOBAL_INIT;
240
14116198
  return airDrandMT_r(airRandMTStateGlobal);
241
}
242
243
/*
244
******** airRandInt
245
**
246
** returns a random integer in range [0, N-1]
247
*/
248
unsigned int
249
airRandInt(unsigned int N) {
250
86099
  _GLOBAL_ALLOC;
251
43050
  _GLOBAL_INIT;
252
43049
  return airUIrandMT_r(airRandMTStateGlobal)%N;
253
}
254
255
unsigned int
256
airRandInt_r(airRandMTState *state, unsigned int N) {
257
258
180
  return airUIrandMT_r(state)%N;
259
}
260
261
/* This checks to see if the sequence of numbers we get is what we
262
   expect.  It should return 1 if all is well, 0 if not.
263
264
   One thing to check for if it fails is the presence of twos
265
   complement interger representation.  The code here relies on it.
266
*/
267
int
268
airRandMTSanity(void) {
269
  int result = 0;
270
  /* Create a new generator with our seed */
271
40
  airRandMTState* rng = airRandMTStateNew(AIR_RANDMT_DEFAULT_SEED);
272
273
20
  if (!rng) {
274
    /* Couldn't allocate memory */
275
    return 0;
276
  }
277
278
  /* Now check against a predetermined list of values; any inequality
279
     will set result to be non-zero */
280
20
  result |= airUIrandMT_r(rng) != 1608637542U;
281
20
  result |= airUIrandMT_r(rng) != 3421126067U;
282
20
  result |= airUIrandMT_r(rng) != 4083286876U;
283
20
  result |= airUIrandMT_r(rng) !=  787846414U;
284
20
  result |= airUIrandMT_r(rng) != 3143890026U;
285
20
  result |= airUIrandMT_r(rng) != 3348747335U;
286
20
  result |= airUIrandMT_r(rng) != 2571218620U;
287
20
  result |= airUIrandMT_r(rng) != 2563451924U;
288
20
  result |= airUIrandMT_r(rng) !=  670094950U;
289
20
  result |= airUIrandMT_r(rng) != 1914837113U;
290
291
20
  airRandMTStateNix(rng);
292
20
  return !result;
293
20
}