Jump to content
  • Advertisement
Sign in to follow this  
Vortez

Mersenne twister bug...

This topic is 2105 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, i've been using this Mersenne twister class in c++, and decided to scan my files using cppcheck, and found a bug, which says

 

Error: Array 'MT[624]' accessed at index 624, which is out of bounds.

 

What's strange is that the error is also in the pseudo code from wikipedia. I also noticed that im starting

at index 1 instead of 0 which is probably another bug (dunno why the hell i did that).

 

Here's my code, it's not very long

#ifndef _CRNG_H_
#define _CRNG_H_
#ifdef __cplusplus

#include "Windows.h"

class CRNG {
public:
	CRNG();
private:
	int MT[624]; 
	int index;

	void GenerateNumbers();
public:
	void InitializeGenerator(int seed);
	int  ExtractNumber();
};

#endif
#endif //_CRNG_H_
#include "RNG.h"

//
CRNG::CRNG()
{
	InitializeGenerator(GetTickCount());
}

// Initialize the generator from a seed
void CRNG::InitializeGenerator(int Seed)
{
	index = 0;
	MT[0] = Seed;
	for(int i = 1; i <= 623; i++){ // loop over each other element
		MT[i] = (1812433253 * (MT[i-1] ^ (MT[i-1] >> 30)) + i);
	}
}


// Extract a tempered pseudorandom number based on the index-th value,
// calling generateNumbers() every 624 numbers
int CRNG::ExtractNumber()
{
	if(index == 0)
		GenerateNumbers();
	
	int y = MT[index];
	y = y ^ (y >> 11);
	y = y ^ ((y << 7) & (2636928640));
	y = y ^ ((y << 15) & (4022730752));
	y = y ^ (y >> 18);
	
	index = (index + 1) % 624;
	return y;
}

// Generate an array of 624 untempered numbers
void CRNG::GenerateNumbers()
{
	for(int i = 1; i <= 623; i++){ 
		
		int y = ((MT[i] & 0x80000000) + (MT[i+1] & 0x7FFFFFFF)) % 624; // <- here's the bug
		
		MT[i] = MT[(i + 397) % 624] ^ (y >> 1);
		
		if((y % 2) == 1) // y is odd
			MT[i] = MT[i] ^ (2567483615);
	}
}

Soo, what's with the buffer overflow? Is it supposed to take MT[0] instead?

 

Thx in advance.

 

EDIT: omg, i misplaced the modulus... and that 'i' should definitively be 0... hope this won't break old projects wacko.png

 

The weird thing is, it worked perfectly for encryption/decryption stuffs and never failed or crashed...

Edited by Vortez

Share this post


Link to post
Share on other sites
Advertisement

Here's the fixed code:

// Generate an array of 624 untempered numbers
void CRNG::GenerateNumbers()
{
	for(int i = 0; i < 624; i++){ 
		
		int y = ((MT[i] & 0x80000000) + (MT[(i+1) % 624] & 0x7FFFFFFF));
		
		MT[i] = MT[(i + 397) % 624] ^ (y >> 1);
		
		if((y % 2) != 0) // y is odd
			MT[i] = MT[i] ^ (0x9908B0DF);
	}
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!