isaac.h revision 12855
112855Sgabeblack@google.com#ifndef __ISAAC_HPP 212855Sgabeblack@google.com#define __ISAAC_HPP 312855Sgabeblack@google.com 412855Sgabeblack@google.com 512855Sgabeblack@google.com/* 612855Sgabeblack@google.com 712855Sgabeblack@google.com C++ TEMPLATE VERSION OF Robert J. Jenkins Jr.'s 812855Sgabeblack@google.com ISAAC Random Number Generator. 912855Sgabeblack@google.com 1012855Sgabeblack@google.com Ported from vanilla C to to template C++ class 1112855Sgabeblack@google.com by Quinn Tyler Jackson on 16-23 July 1998. 1212855Sgabeblack@google.com 1312855Sgabeblack@google.com quinn@qtj.net 1412855Sgabeblack@google.com 1512855Sgabeblack@google.com The function for the expected period of this 1612855Sgabeblack@google.com random number generator, according to Jenkins is: 1712855Sgabeblack@google.com 1812855Sgabeblack@google.com f(a,b) = 2**((a+b*(3+2^^a)-1) 1912855Sgabeblack@google.com 2012855Sgabeblack@google.com (where a is ALPHA and b is bitwidth) 2112855Sgabeblack@google.com 2212855Sgabeblack@google.com So, for a bitwidth of 32 and an ALPHA of 8, 2312855Sgabeblack@google.com the expected period of ISAAC is: 2412855Sgabeblack@google.com 2512855Sgabeblack@google.com 2^^(8+32*(3+2^^8)-1) = 2^^8295 2612855Sgabeblack@google.com 2712855Sgabeblack@google.com Jackson has been able to run implementations 2812855Sgabeblack@google.com with an ALPHA as high as 16, or 2912855Sgabeblack@google.com 3012855Sgabeblack@google.com 2^^2097263 3112855Sgabeblack@google.com 3212855Sgabeblack@google.com*/ 3312855Sgabeblack@google.com 3412855Sgabeblack@google.com 3512855Sgabeblack@google.comtypedef unsigned int UINT32; 3612855Sgabeblack@google.comconst UINT32 GOLDEN_RATIO = UINT32(0x9e3779b9); 3712855Sgabeblack@google.com 3812855Sgabeblack@google.com 3912855Sgabeblack@google.comtemplate <UINT32 ALPHA = (8)> 4012855Sgabeblack@google.comclass QTIsaac 4112855Sgabeblack@google.com{ 4212855Sgabeblack@google.com public: 4312855Sgabeblack@google.com 4412855Sgabeblack@google.com typedef unsigned char byte; 4512855Sgabeblack@google.com 4612855Sgabeblack@google.com struct randctx 4712855Sgabeblack@google.com { 4812855Sgabeblack@google.com randctx(void) 4912855Sgabeblack@google.com { 5012855Sgabeblack@google.com randrsl = new UINT32[N]; 5112855Sgabeblack@google.com randmem = new UINT32[N]; 5212855Sgabeblack@google.com } 5312855Sgabeblack@google.com 5412855Sgabeblack@google.com ~randctx(void) 5512855Sgabeblack@google.com { 5612855Sgabeblack@google.com delete [] randrsl; 5712855Sgabeblack@google.com delete [] randmem; 5812855Sgabeblack@google.com } 5912855Sgabeblack@google.com 6012855Sgabeblack@google.com UINT32 randcnt; 6112855Sgabeblack@google.com UINT32* randrsl; 6212855Sgabeblack@google.com UINT32* randmem; 6312855Sgabeblack@google.com UINT32 randa; 6412855Sgabeblack@google.com UINT32 randb; 6512855Sgabeblack@google.com UINT32 randc; 6612855Sgabeblack@google.com }; 6712855Sgabeblack@google.com 6812855Sgabeblack@google.com QTIsaac(UINT32 a = 0, UINT32 b = 0, UINT32 c = 0); 6912855Sgabeblack@google.com virtual ~QTIsaac(void); 7012855Sgabeblack@google.com 7112855Sgabeblack@google.com UINT32 rand(void); 7212855Sgabeblack@google.com virtual void randinit(randctx* ctx, bool bUseSeed); 7312855Sgabeblack@google.com virtual void srand( 7412855Sgabeblack@google.com UINT32 a = 0, UINT32 b = 0, UINT32 c = 0, UINT32* s = NULL); 7512855Sgabeblack@google.com 7612855Sgabeblack@google.com enum {N = (1<<ALPHA)}; 7712855Sgabeblack@google.com 7812855Sgabeblack@google.com protected: 7912855Sgabeblack@google.com 8012855Sgabeblack@google.com virtual void isaac(randctx* ctx); 8112855Sgabeblack@google.com 8212855Sgabeblack@google.com UINT32 ind(UINT32* mm, UINT32 x); 8312855Sgabeblack@google.com void rngstep( 8412855Sgabeblack@google.com UINT32 mix, UINT32& a, UINT32& b, UINT32*& mm, UINT32*& m, 8512855Sgabeblack@google.com UINT32*& m2, UINT32*& r, UINT32& x, UINT32& y); 8612855Sgabeblack@google.com virtual void shuffle( 8712855Sgabeblack@google.com UINT32& a, UINT32& b, UINT32& c, UINT32& d, UINT32& e, UINT32& f, 8812855Sgabeblack@google.com UINT32& g, UINT32& h); 8912855Sgabeblack@google.com 9012855Sgabeblack@google.com private: 9112855Sgabeblack@google.com randctx m_rc; 9212855Sgabeblack@google.com}; 9312855Sgabeblack@google.com 9412855Sgabeblack@google.com 9512855Sgabeblack@google.comtemplate<UINT32 ALPHA> 9612855Sgabeblack@google.comQTIsaac<ALPHA>::QTIsaac(UINT32 a, UINT32 b, UINT32 c) : m_rc() 9712855Sgabeblack@google.com{ 9812855Sgabeblack@google.com srand(a, b, c); 9912855Sgabeblack@google.com} 10012855Sgabeblack@google.com 10112855Sgabeblack@google.com 10212855Sgabeblack@google.comtemplate<UINT32 ALPHA> 10312855Sgabeblack@google.comQTIsaac<ALPHA>::~QTIsaac(void) 10412855Sgabeblack@google.com{ 10512855Sgabeblack@google.com // DO NOTHING 10612855Sgabeblack@google.com} 10712855Sgabeblack@google.com 10812855Sgabeblack@google.com 10912855Sgabeblack@google.comtemplate<UINT32 ALPHA> 11012855Sgabeblack@google.comvoid QTIsaac<ALPHA>::srand(UINT32 a, UINT32 b, UINT32 c, UINT32* s) 11112855Sgabeblack@google.com{ 11212855Sgabeblack@google.com for(int i = 0; i < N; i++) 11312855Sgabeblack@google.com { 11412855Sgabeblack@google.com m_rc.randrsl[i] = s != NULL ? s[i] : 0; 11512855Sgabeblack@google.com } 11612855Sgabeblack@google.com 11712855Sgabeblack@google.com m_rc.randa = a; 11812855Sgabeblack@google.com m_rc.randb = b; 11912855Sgabeblack@google.com m_rc.randc = c; 12012855Sgabeblack@google.com 12112855Sgabeblack@google.com randinit(&m_rc, true); 12212855Sgabeblack@google.com} 12312855Sgabeblack@google.com 12412855Sgabeblack@google.com 12512855Sgabeblack@google.comtemplate<UINT32 ALPHA> 12612855Sgabeblack@google.cominline UINT32 QTIsaac<ALPHA>::rand(void) 12712855Sgabeblack@google.com{ 12812855Sgabeblack@google.com return 0x7fffffff & (!m_rc.randcnt-- ? 12912855Sgabeblack@google.com (isaac(&m_rc), m_rc.randcnt=(N-1), m_rc.randrsl[m_rc.randcnt]) : 13012855Sgabeblack@google.com m_rc.randrsl[m_rc.randcnt]); 13112855Sgabeblack@google.com} 13212855Sgabeblack@google.com 13312855Sgabeblack@google.com 13412855Sgabeblack@google.comtemplate<UINT32 ALPHA> 13512855Sgabeblack@google.cominline void QTIsaac<ALPHA>::randinit(randctx* ctx, bool bUseSeed) 13612855Sgabeblack@google.com{ 13712855Sgabeblack@google.com UINT32 a,b,c,d,e,f,g,h; 13812855Sgabeblack@google.com int i; 13912855Sgabeblack@google.com 14012855Sgabeblack@google.com a = b = c = d = e = f = g = h = GOLDEN_RATIO; 14112855Sgabeblack@google.com 14212855Sgabeblack@google.com UINT32* m = (ctx->randmem); 14312855Sgabeblack@google.com UINT32* r = (ctx->randrsl); 14412855Sgabeblack@google.com 14512855Sgabeblack@google.com if(!bUseSeed) 14612855Sgabeblack@google.com { 14712855Sgabeblack@google.com ctx->randa = 0; 14812855Sgabeblack@google.com ctx->randb = 0; 14912855Sgabeblack@google.com ctx->randc = 0; 15012855Sgabeblack@google.com } 15112855Sgabeblack@google.com 15212855Sgabeblack@google.com // scramble it 15312855Sgabeblack@google.com for(i=0; i < 4; ++i) 15412855Sgabeblack@google.com { 15512855Sgabeblack@google.com shuffle(a,b,c,d,e,f,g,h); 15612855Sgabeblack@google.com } 15712855Sgabeblack@google.com 15812855Sgabeblack@google.com if(bUseSeed) 15912855Sgabeblack@google.com { 16012855Sgabeblack@google.com // initialize using the contents of r[] as the seed 16112855Sgabeblack@google.com 16212855Sgabeblack@google.com for(i=0; i < N; i+=8) 16312855Sgabeblack@google.com { 16412855Sgabeblack@google.com a+=r[i ]; b+=r[i+1]; c+=r[i+2]; d+=r[i+3]; 16512855Sgabeblack@google.com e+=r[i+4]; f+=r[i+5]; g+=r[i+6]; h+=r[i+7]; 16612855Sgabeblack@google.com 16712855Sgabeblack@google.com shuffle(a,b,c,d,e,f,g,h); 16812855Sgabeblack@google.com 16912855Sgabeblack@google.com m[i ]=a; m[i+1]=b; m[i+2]=c; m[i+3]=d; 17012855Sgabeblack@google.com m[i+4]=e; m[i+5]=f; m[i+6]=g; m[i+7]=h; 17112855Sgabeblack@google.com } 17212855Sgabeblack@google.com 17312855Sgabeblack@google.com //do a second pass to make all of the seed affect all of m 17412855Sgabeblack@google.com 17512855Sgabeblack@google.com for(i=0; i < N; i += 8) 17612855Sgabeblack@google.com { 17712855Sgabeblack@google.com a+=m[i ]; b+=m[i+1]; c+=m[i+2]; d+=m[i+3]; 17812855Sgabeblack@google.com e+=m[i+4]; f+=m[i+5]; g+=m[i+6]; h+=m[i+7]; 17912855Sgabeblack@google.com 18012855Sgabeblack@google.com shuffle(a,b,c,d,e,f,g,h); 18112855Sgabeblack@google.com 18212855Sgabeblack@google.com m[i ]=a; m[i+1]=b; m[i+2]=c; m[i+3]=d; 18312855Sgabeblack@google.com m[i+4]=e; m[i+5]=f; m[i+6]=g; m[i+7]=h; 18412855Sgabeblack@google.com } 18512855Sgabeblack@google.com } 18612855Sgabeblack@google.com else 18712855Sgabeblack@google.com { 18812855Sgabeblack@google.com // fill in mm[] with messy stuff 18912855Sgabeblack@google.com 19012855Sgabeblack@google.com shuffle(a,b,c,d,e,f,g,h); 19112855Sgabeblack@google.com 19212855Sgabeblack@google.com m[i ]=a; m[i+1]=b; m[i+2]=c; m[i+3]=d; 19312855Sgabeblack@google.com m[i+4]=e; m[i+5]=f; m[i+6]=g; m[i+7]=h; 19412855Sgabeblack@google.com 19512855Sgabeblack@google.com } 19612855Sgabeblack@google.com 19712855Sgabeblack@google.com isaac(ctx); // fill in the first set of results 19812855Sgabeblack@google.com ctx->randcnt = N; // prepare to use the first set of results 19912855Sgabeblack@google.com} 20012855Sgabeblack@google.com 20112855Sgabeblack@google.com 20212855Sgabeblack@google.comtemplate<UINT32 ALPHA> 20312855Sgabeblack@google.cominline UINT32 QTIsaac<ALPHA>::ind(UINT32* mm, UINT32 x) 20412855Sgabeblack@google.com{ 20512855Sgabeblack@google.com return (*(UINT32*)((byte*)(mm) + ((x) & ((N-1)<<2)))); 20612855Sgabeblack@google.com} 20712855Sgabeblack@google.com 20812855Sgabeblack@google.com 20912855Sgabeblack@google.comtemplate<UINT32 ALPHA> 21012855Sgabeblack@google.cominline void QTIsaac<ALPHA>::rngstep(UINT32 mix, UINT32& a, UINT32& b, UINT32*& mm, UINT32*& m, UINT32*& m2, UINT32*& r, UINT32& x, UINT32& y) 21112855Sgabeblack@google.com{ 21212855Sgabeblack@google.com x = *m; 21312855Sgabeblack@google.com a = (a^(mix)) + *(m2++); 21412855Sgabeblack@google.com *(m++) = y = ind(mm,x) + a + b; 21512855Sgabeblack@google.com *(r++) = b = ind(mm,y>>ALPHA) + x; 21612855Sgabeblack@google.com} 21712855Sgabeblack@google.com 21812855Sgabeblack@google.com 21912855Sgabeblack@google.comtemplate<UINT32 ALPHA> 22012855Sgabeblack@google.cominline void QTIsaac<ALPHA>::shuffle(UINT32& a, UINT32& b, UINT32& c, UINT32& d, UINT32& e, UINT32& f, UINT32& g, UINT32& h) 22112855Sgabeblack@google.com{ 22212855Sgabeblack@google.com a^=b<<11; d+=a; b+=c; 22312855Sgabeblack@google.com b^=c>>2; e+=b; c+=d; 22412855Sgabeblack@google.com c^=d<<8; f+=c; d+=e; 22512855Sgabeblack@google.com d^=e>>16; g+=d; e+=f; 22612855Sgabeblack@google.com e^=f<<10; h+=e; f+=g; 22712855Sgabeblack@google.com f^=g>>4; a+=f; g+=h; 22812855Sgabeblack@google.com g^=h<<8; b+=g; h+=a; 22912855Sgabeblack@google.com h^=a>>9; c+=h; a+=b; 23012855Sgabeblack@google.com} 23112855Sgabeblack@google.com 23212855Sgabeblack@google.com 23312855Sgabeblack@google.comtemplate<UINT32 ALPHA> 23412855Sgabeblack@google.cominline void QTIsaac<ALPHA>::isaac(randctx* ctx) 23512855Sgabeblack@google.com{ 23612855Sgabeblack@google.com UINT32 x,y; 23712855Sgabeblack@google.com 23812855Sgabeblack@google.com UINT32* mm = ctx->randmem; 23912855Sgabeblack@google.com UINT32* r = ctx->randrsl; 24012855Sgabeblack@google.com 24112855Sgabeblack@google.com UINT32 a = (ctx->randa); 24212855Sgabeblack@google.com UINT32 b = (ctx->randb + (++ctx->randc)); 24312855Sgabeblack@google.com 24412855Sgabeblack@google.com UINT32* m = mm; 24512855Sgabeblack@google.com UINT32* m2 = (m+(N/2)); 24612855Sgabeblack@google.com UINT32* mend = m2; 24712855Sgabeblack@google.com 24812855Sgabeblack@google.com for(; m<mend; ) 24912855Sgabeblack@google.com { 25012855Sgabeblack@google.com rngstep((a<<13), a, b, mm, m, m2, r, x, y); 25112855Sgabeblack@google.com rngstep((a>>6) , a, b, mm, m, m2, r, x, y); 25212855Sgabeblack@google.com rngstep((a<<2) , a, b, mm, m, m2, r, x, y); 25312855Sgabeblack@google.com rngstep((a>>16), a, b, mm, m, m2, r, x, y); 25412855Sgabeblack@google.com } 25512855Sgabeblack@google.com 25612855Sgabeblack@google.com m2 = mm; 25712855Sgabeblack@google.com 25812855Sgabeblack@google.com for(; m2<mend; ) 25912855Sgabeblack@google.com { 26012855Sgabeblack@google.com rngstep((a<<13), a, b, mm, m, m2, r, x, y); 26112855Sgabeblack@google.com rngstep((a>>6) , a, b, mm, m, m2, r, x, y); 26212855Sgabeblack@google.com rngstep((a<<2) , a, b, mm, m, m2, r, x, y); 26312855Sgabeblack@google.com rngstep((a>>16), a, b, mm, m, m2, r, x, y); 26412855Sgabeblack@google.com } 26512855Sgabeblack@google.com 26612855Sgabeblack@google.com ctx->randb = b; 26712855Sgabeblack@google.com ctx->randa = a; 26812855Sgabeblack@google.com} 26912855Sgabeblack@google.com 27012855Sgabeblack@google.com 27112855Sgabeblack@google.com#endif // __ISAAC_HPP 27212855Sgabeblack@google.com 273