(C++) random character/number generator

[jam]

As Bitplane has pointed out rand() differs across systems even if you set the same seed, I however needed something a little more random.

Code: Select all

//RandPool.h


#ifndef RANDPOOLINCLUDED
#define RANDPOOLINCLUDED

#define byte unsigned char
#define word32 unsigned int

//The size of the random pool
#define RANDPOOLBITS 3072

//This is a parameter of the the MD5 algorithm
#define RANDKEYWORDS 16

//The pool must be a multiple of the 16-byte (128-bit) MD5 block size
#define RANDPOOLWORDS ((RANDPOOLBITS+127 & ~127) >> 5)

#if RANDPOOLWORDS <= RANDKEYWORDS
#error Random pool too small - please increase RANDPOOLBITS in randpool.h
#endif

class RandPool
{
public:
	RandPool();
	void Stir();
	void AddBytes(byte const *buf, unsigned len);
	void GetBytes(byte *buf, unsigned len);
	byte GetByte();
private:
	//Must be word-aligned, so make it words. Cast to bytes as needed.
	word32 randPool[RANDPOOLWORDS];	//Random pool
	word32 randKey[RANDKEYWORDS];	//Next stirring key
	unsigned randPoolGetPos;		//Position to get from
	unsigned randKeyAddPos;			//Position to add to
};

#endif

Code: Select all

/*
The user of this class really only needs to know how to work
three functions -
AddBytes, which feeds data to the pool. Mixing is automatic.
GetByte, which outputs a single byte of pseudo-random data.
GetBytes, which outputs a stream of pseudo-random data.
*/

#include <stdlib.h>
#include <string.h>
#include "randpool.h"

void byteSwap(word32 *buf, unsigned words)
{
    byte *p = (byte *)buf;
    do
    {
        *buf++ = (word32)((unsigned)p[3]<<8 | p[2]) << 16 | ((unsigned) p[1]  << 8 | p[0]);
         p += 4;
    }
    while (--words);
}

//The four core functions 
#define F1(x, y, z) (z ^ (x & (y ^ z)))
#define F2(x, y, z) F1(z, x, y)
#define F3(x, y, z) (x ^ y ^ z)
#define F4(x, y, z) (y ^ (x | ~z))

//This is the central step in the MD5 algorithm.
#define MD5STEP(f,w,x,y,z,in,s) (w += f(x,y,z)+in, w = (w<<s | w>>32-s) + x)

/* The heart of the MD5 algorithm, this alters an existing MD5 hash to
 * reflect the addition of 16 words of new data.  MD5Update blocks the
 * data and converts bytes into 32-bit words for this routine.
 */
void MD5Transform(word32 hash[4], word32 const input[16])
{
	register word32 a = hash[0], b = hash[1], c = hash[2], d = hash[3];

	MD5STEP(F1, a, b, c, d, input[ 0]+0xd76aa478,  7);
	MD5STEP(F1, d, a, b, c, input[ 1]+0xe8c7b756, 12);
	MD5STEP(F1, c, d, a, b, input[ 2]+0x242070db, 17);
	MD5STEP(F1, b, c, d, a, input[ 3]+0xc1bdceee, 22);
	MD5STEP(F1, a, b, c, d, input[ 4]+0xf57c0faf,  7);
	MD5STEP(F1, d, a, b, c, input[ 5]+0x4787c62a, 12);
	MD5STEP(F1, c, d, a, b, input[ 6]+0xa8304613, 17);
	MD5STEP(F1, b, c, d, a, input[ 7]+0xfd469501, 22);
	MD5STEP(F1, a, b, c, d, input[ 8]+0x698098d8,  7);
	MD5STEP(F1, d, a, b, c, input[ 9]+0x8b44f7af, 12);
	MD5STEP(F1, c, d, a, b, input[10]+0xffff5bb1, 17);
	MD5STEP(F1, b, c, d, a, input[11]+0x895cd7be, 22);
	MD5STEP(F1, a, b, c, d, input[12]+0x6b901122,  7);
	MD5STEP(F1, d, a, b, c, input[13]+0xfd987193, 12);
	MD5STEP(F1, c, d, a, b, input[14]+0xa679438e, 17);
	MD5STEP(F1, b, c, d, a, input[15]+0x49b40821, 22);

	MD5STEP(F2, a, b, c, d, input[ 1]+0xf61e2562,  5);
	MD5STEP(F2, d, a, b, c, input[ 6]+0xc040b340,  9);
	MD5STEP(F2, c, d, a, b, input[11]+0x265e5a51, 14);
	MD5STEP(F2, b, c, d, a, input[ 0]+0xe9b6c7aa, 20);
	MD5STEP(F2, a, b, c, d, input[ 5]+0xd62f105d,  5);
	MD5STEP(F2, d, a, b, c, input[10]+0x02441453,  9);
	MD5STEP(F2, c, d, a, b, input[15]+0xd8a1e681, 14);
	MD5STEP(F2, b, c, d, a, input[ 4]+0xe7d3fbc8, 20);
	MD5STEP(F2, a, b, c, d, input[ 9]+0x21e1cde6,  5);
	MD5STEP(F2, d, a, b, c, input[14]+0xc33707d6,  9);
	MD5STEP(F2, c, d, a, b, input[ 3]+0xf4d50d87, 14);
	MD5STEP(F2, b, c, d, a, input[ 8]+0x455a14ed, 20);
	MD5STEP(F2, a, b, c, d, input[13]+0xa9e3e905,  5);
	MD5STEP(F2, d, a, b, c, input[ 2]+0xfcefa3f8,  9);
	MD5STEP(F2, c, d, a, b, input[ 7]+0x676f02d9, 14);
	MD5STEP(F2, b, c, d, a, input[12]+0x8d2a4c8a, 20);

	MD5STEP(F3, a, b, c, d, input[ 5]+0xfffa3942,  4);
	MD5STEP(F3, d, a, b, c, input[ 8]+0x8771f681, 11);
	MD5STEP(F3, c, d, a, b, input[11]+0x6d9d6122, 16);
	MD5STEP(F3, b, c, d, a, input[14]+0xfde5380c, 23);
	MD5STEP(F3, a, b, c, d, input[ 1]+0xa4beea44,  4);
	MD5STEP(F3, d, a, b, c, input[ 4]+0x4bdecfa9, 11);
	MD5STEP(F3, c, d, a, b, input[ 7]+0xf6bb4b60, 16);
	MD5STEP(F3, b, c, d, a, input[10]+0xbebfbc70, 23);
	MD5STEP(F3, a, b, c, d, input[13]+0x289b7ec6,  4);
	MD5STEP(F3, d, a, b, c, input[ 0]+0xeaa127fa, 11);
	MD5STEP(F3, c, d, a, b, input[ 3]+0xd4ef3085, 16);
	MD5STEP(F3, b, c, d, a, input[ 6]+0x04881d05, 23);
	MD5STEP(F3, a, b, c, d, input[ 9]+0xd9d4d039,  4);
	MD5STEP(F3, d, a, b, c, input[12]+0xe6db99e5, 11);
	MD5STEP(F3, c, d, a, b, input[15]+0x1fa27cf8, 16);
	MD5STEP(F3, b, c, d, a, input[ 2]+0xc4ac5665, 23);

	MD5STEP(F4, a, b, c, d, input[ 0]+0xf4292244,  6);
	MD5STEP(F4, d, a, b, c, input[ 7]+0x432aff97, 10);
	MD5STEP(F4, c, d, a, b, input[14]+0xab9423a7, 15);
	MD5STEP(F4, b, c, d, a, input[ 5]+0xfc93a039, 21);
	MD5STEP(F4, a, b, c, d, input[12]+0x655b59c3,  6);
	MD5STEP(F4, d, a, b, c, input[ 3]+0x8f0ccc92, 10);
	MD5STEP(F4, c, d, a, b, input[10]+0xffeff47d, 15);
	MD5STEP(F4, b, c, d, a, input[ 1]+0x85845dd1, 21);
	MD5STEP(F4, a, b, c, d, input[ 8]+0x6fa87e4f,  6);
	MD5STEP(F4, d, a, b, c, input[15]+0xfe2ce6e0, 10);
	MD5STEP(F4, c, d, a, b, input[ 6]+0xa3014314, 15);
	MD5STEP(F4, b, c, d, a, input[13]+0x4e0811a1, 21);
	MD5STEP(F4, a, b, c, d, input[ 4]+0xf7537e82,  6);
	MD5STEP(F4, d, a, b, c, input[11]+0xbd3af235, 10);
	MD5STEP(F4, c, d, a, b, input[ 2]+0x2ad7d2bb, 15);
	MD5STEP(F4, b, c, d, a, input[ 9]+0xeb86d391, 21);

	hash[0] += a;
	hash[1] += b;
	hash[2] += c;
	hash[3] += d;
}

RandPool::RandPool() 
{
	//Make sure the pool is empty here, so that, given any
	//class instance, input data will consistently generate
	//corresponding output data.
	int ind;
        randPoolGetPos = sizeof(randPool);
	randKeyAddPos = 0;
	for (ind = 0; ind < RANDPOOLWORDS; ind++)
       {
            randPool[ind] = 0;
       }
	
       for (ind = 0; ind < RANDKEYWORDS; ind++)
       {
            randKey[ind] = 0;
       }
}

void RandPool::Stir()
{
	int i;
	word32 iv[4];

	//Convert to word32s for stirring operation
	byteSwap(randPool, RANDPOOLWORDS);
	byteSwap(randKey, RANDKEYWORDS);

	//Start IV from last block of randPool
	memcpy(iv, randPool+RANDPOOLWORDS-4, sizeof(iv));

	//CFB pass
	for (i = 0; i < RANDPOOLWORDS; i += 4)
       {
		MD5Transform(iv, randKey);
		iv[0] = randPool[i  ] ^= iv[0];
		iv[1] = randPool[i+1] ^= iv[1];
		iv[2] = randPool[i+2] ^= iv[2];
		iv[3] = randPool[i+3] ^= iv[3];
	}

	//Wipe iv from memory
	memset(iv, 0, sizeof(iv));

	//Convert randPool back to bytes for further use
	byteSwap(randPool, RANDPOOLWORDS);

	//Get new key
	memcpy(randKey, randPool, sizeof(randKey));

	//Set up pointers for future addition or removal of random bytes
	randKeyAddPos = 0;
	randPoolGetPos = sizeof(randKey);
}

void RandPool::AddBytes(byte const *buf, unsigned len)
{
	byte *p = (byte *)randKey+randKeyAddPos;
	unsigned t = sizeof(randKey) - randKeyAddPos;

	while (len > t)
       {
		len -= t;
		while (t--)
               {
			*p++ ^= *buf++;
               }
		Stir();		//Sets randKeyAddPos to 0
		p = (byte *)randKey;
		t = sizeof(randKey);
	}

      if (len)
      {
		randKeyAddPos += len;
		do
			*p++ ^= *buf++;
		while (--len);
		randPoolGetPos = sizeof(randPool); //Force stir on get
	}
}

void RandPool::GetBytes(byte *buf, unsigned len) 
{
	unsigned t;

	while (len > (t = sizeof(randPool) - randPoolGetPos)) 
       {
		memcpy(buf, (byte const *)randPool+randPoolGetPos, t);
		buf += t;
		len -= t;
		Stir();
	}

	memcpy(buf, (byte const *)randPool+randPoolGetPos, len);
	randPoolGetPos += len;
}

byte RandPool::GetByte()
{
	if (randPoolGetPos == sizeof(randPool))
       {
		Stir();
       }

	return ((byte const *)randPool)[randPoolGetPos++];
}

[bitplane]

Very cool, much better than mine! I think I'll use yours

[Spintz]

I think I'll stick with rand()!

Cross Platform is great and all, but reinventing the wheel for everything that needs to be done, is not.

[bitplane]

hmm sometimes you need square wheels tho

[jam]

Cross Platform is great and all, but reinventing the wheel for everything that needs to be done, is not.

No, reinventing the wheel here. As I said I needed something that was more random and rand() for all it's strengths is not very random at all and I was willing to take a performance hit to achieve what I needed.

[Midnight]

right he didn't reinvent the wheel here he just rubberized them.

nothing wrong with evolution and obviously this is only for those that need it. nice work I may have a use for this someday.

[Veylon]

I'll take it. There are some situations in which you might need a cross-platform random number generator. Any kind of game that needs to stay synchronized without lots of net traffic.

[lug]

How do you use this? I think I'm using it correctly:

Code: Select all

RandPool randomPool;

const unsigned char var[4] = "foo";

randomPool.AddBytes(var,1024);

unsigned char randomValue1 = randomPool.GetByte();
unsigned char randomValue2 = randomPool.GetByte();
unsigned char randomValue3 = randomPool.GetByte();
unsigned char randomValue4 = randomPool.GetByte();

Sorry, lug is slow.

Oh, also why is "Stir()" declared public when it's already called internally by "AddBytes()"?

[jam]

How do you use this? I think I'm using it correctly:

Code: Select all

randomPool.AddBytes(var,1024);

The number is for the length of the input string in the case of "foo" it's 3.

Oh, also why is "Stir()" declared public when it's already called internally by "AddBytes()"?

A situation might arise where you need to manually mix the random pool, the stir function is made public to allow you to do this.