Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
Sync mersenne-twister with upstream
Includes fixes for out-of-bounds read and incorrect generation
of numbers
  • Loading branch information
nyalldawson committed Feb 17, 2015
1 parent e2dd504 commit 58a68b6
Show file tree
Hide file tree
Showing 2 changed files with 34 additions and 29 deletions.
59 changes: 31 additions & 28 deletions src/analysis/vector/mersenne-twister.cpp
Expand Up @@ -13,11 +13,11 @@
* http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf
*
* Written by Christian Stigen Larsen
* http://csl.sublevel3.org
* http://csl.name
*
* Distributed under the modified BSD license.
*
* 2012-01-11
* 2015-02-17
*/

#include <stdio.h>
Expand All @@ -39,6 +39,11 @@ static unsigned index = 0;
#define L31(x) (0x7FFFFFFF & x) // 31 Least Significant Bits
#define ODD(x) (x & 1) // Check if number is odd

#define UNROLL(expr) \
y = M32(MT[i]) | L31(MT[i+1]); \
MT[i] = MT[expr] ^ (y>>1) ^ MATRIX[ODD(y)]; \
++i;

#define MD_UINT32_MAX std::numeric_limits<uint32_t>::max()

static inline void generate_numbers()
Expand All @@ -62,46 +67,44 @@ static inline void generate_numbers()
*/

static const uint32_t MATRIX[2] = {0, 0x9908b0df};
register uint32_t y, i;
register uint32_t y, i = 0;

// i = [0 ... 226]
for ( i = 0; i < DIFF; ++i )
while ( i < ( DIFF - 1 ) )
{
/*
* We're doing 226 = 113*2, an even number of steps, so we can
* safely unroll one more step here for speed:
*/
y = M32( MT[i] ) | L31( MT[i+1] );
MT[i] = MT[i+PERIOD] ^( y >> 1 ) ^ MATRIX[ODD( y )];

++i;
y = M32( MT[i] ) | L31( MT[i+1] );
MT[i] = MT[i+PERIOD] ^( y >> 1 ) ^ MATRIX[ODD( y )];
UNROLL( i + PERIOD );
UNROLL( i + PERIOD );
}

#define UNROLL \
y = M32(MT[i]) | L31(MT[i+1]); \
MT[i] = MT[i-DIFF] ^ (y>>1) ^ MATRIX[ODD(y)]; \
++i;
// i = 226
UNROLL(( i + PERIOD ) % SIZE );

// i = [227 ... 622]
for ( i = DIFF; i < ( SIZE - 1 ); )
while ( i < ( SIZE - 1 ) )
{
/*
* 623-227 = 396 = 2*2*3*3*11, so we can unroll this loop in any
* number that evenly divides 396 (2, 4, 6, etc).
* 623-227 = 396 = 2*2*3*3*11, so we can unroll this loop in any number
* that evenly divides 396 (2, 4, 6, etc). Here we'll unroll 11 times.
*/

// 11 times
UNROLL; UNROLL; UNROLL;
UNROLL; UNROLL; UNROLL;

UNROLL; UNROLL; UNROLL;
UNROLL; UNROLL;
UNROLL( i - DIFF );
UNROLL( i - DIFF );
UNROLL( i - DIFF );
UNROLL( i - DIFF );
UNROLL( i - DIFF );
UNROLL( i - DIFF );
UNROLL( i - DIFF );
UNROLL( i - DIFF );
UNROLL( i - DIFF );
UNROLL( i - DIFF );
UNROLL( i - DIFF );
}

// i = [623]
y = M32( MT[SIZE-1] ) | L31( MT[SIZE-1] );
// i = 623
y = M32( MT[SIZE-1] ) | L31( MT[0] );
MT[SIZE-1] = MT[PERIOD-1] ^( y >> 1 ) ^ MATRIX[ODD( y )];
}

Expand Down Expand Up @@ -135,8 +138,8 @@ extern "C" void seed( uint32_t value )
* "A common Mersenne twister implementation, interestingly
* enough, uses an LCG to generate seed data.",
*
* Since our we're using 32-bits data types for our MT array,
* we can skip the masking with 0xFFFFFFFF below.
* Since we're using 32-bits data types for our MT array, we can skip the
* masking with 0xFFFFFFFF below.
*/

MT[0] = value;
Expand Down
4 changes: 3 additions & 1 deletion src/analysis/vector/mersenne-twister.h
Expand Up @@ -14,9 +14,11 @@
* namespace.
*
* Written by Christian Stigen Larsen
* 2012-01-11 -- http://csl.sublevel3.org
* http://csl.name
*
* Distributed under the modified BSD license.
*
* 2015-02-17
*/

#ifndef MERSENNE_TWISTER_H
Expand Down

0 comments on commit 58a68b6

Please sign in to comment.