isaac.h revision 12855:588919e0e4aa
112150Sgabor.dozsa@arm.com#ifndef __ISAAC_HPP 212150Sgabor.dozsa@arm.com#define __ISAAC_HPP 312150Sgabor.dozsa@arm.com 412150Sgabor.dozsa@arm.com 512150Sgabor.dozsa@arm.com/* 612150Sgabor.dozsa@arm.com 712150Sgabor.dozsa@arm.com C++ TEMPLATE VERSION OF Robert J. Jenkins Jr.'s 812150Sgabor.dozsa@arm.com ISAAC Random Number Generator. 912150Sgabor.dozsa@arm.com 1012150Sgabor.dozsa@arm.com Ported from vanilla C to to template C++ class 1112150Sgabor.dozsa@arm.com by Quinn Tyler Jackson on 16-23 July 1998. 1212150Sgabor.dozsa@arm.com 1312150Sgabor.dozsa@arm.com quinn@qtj.net 1412150Sgabor.dozsa@arm.com 1512150Sgabor.dozsa@arm.com The function for the expected period of this 1612150Sgabor.dozsa@arm.com random number generator, according to Jenkins is: 1712150Sgabor.dozsa@arm.com 1812150Sgabor.dozsa@arm.com f(a,b) = 2**((a+b*(3+2^^a)-1) 1912150Sgabor.dozsa@arm.com 2012150Sgabor.dozsa@arm.com (where a is ALPHA and b is bitwidth) 2112150Sgabor.dozsa@arm.com 2212150Sgabor.dozsa@arm.com So, for a bitwidth of 32 and an ALPHA of 8, 2312150Sgabor.dozsa@arm.com the expected period of ISAAC is: 2412150Sgabor.dozsa@arm.com 2512150Sgabor.dozsa@arm.com 2^^(8+32*(3+2^^8)-1) = 2^^8295 2612150Sgabor.dozsa@arm.com 2712150Sgabor.dozsa@arm.com Jackson has been able to run implementations 2812150Sgabor.dozsa@arm.com with an ALPHA as high as 16, or 2912150Sgabor.dozsa@arm.com 3012150Sgabor.dozsa@arm.com 2^^2097263 3112150Sgabor.dozsa@arm.com 3212150Sgabor.dozsa@arm.com*/ 3312150Sgabor.dozsa@arm.com 3412150Sgabor.dozsa@arm.com 3512150Sgabor.dozsa@arm.comtypedef unsigned int UINT32; 3612150Sgabor.dozsa@arm.comconst UINT32 GOLDEN_RATIO = UINT32(0x9e3779b9); 3712150Sgabor.dozsa@arm.com 3812150Sgabor.dozsa@arm.com 3912150Sgabor.dozsa@arm.comtemplate <UINT32 ALPHA = (8)> 4012150Sgabor.dozsa@arm.comclass QTIsaac 4112150Sgabor.dozsa@arm.com{ 4212150Sgabor.dozsa@arm.com public: 4312150Sgabor.dozsa@arm.com 4412150Sgabor.dozsa@arm.com typedef unsigned char byte; 4512150Sgabor.dozsa@arm.com 4612564Sgabeblack@google.com struct randctx 4713774Sandreas.sandberg@arm.com { 4812564Sgabeblack@google.com randctx(void) 4912150Sgabor.dozsa@arm.com { 5012150Sgabor.dozsa@arm.com randrsl = new UINT32[N]; 5112150Sgabor.dozsa@arm.com randmem = new UINT32[N]; 5212150Sgabor.dozsa@arm.com } 5313609Sgiacomo.travaglini@arm.com 5412150Sgabor.dozsa@arm.com ~randctx(void) 5512150Sgabor.dozsa@arm.com { 5612150Sgabor.dozsa@arm.com delete [] randrsl; 5712150Sgabor.dozsa@arm.com delete [] randmem; 5812150Sgabor.dozsa@arm.com } 5912150Sgabor.dozsa@arm.com 6012150Sgabor.dozsa@arm.com UINT32 randcnt; 6112150Sgabor.dozsa@arm.com UINT32* randrsl; 6212150Sgabor.dozsa@arm.com UINT32* randmem; 6312150Sgabor.dozsa@arm.com UINT32 randa; 6412150Sgabor.dozsa@arm.com UINT32 randb; 6512150Sgabor.dozsa@arm.com UINT32 randc; 6612150Sgabor.dozsa@arm.com }; 6712150Sgabor.dozsa@arm.com 6812150Sgabor.dozsa@arm.com QTIsaac(UINT32 a = 0, UINT32 b = 0, UINT32 c = 0); 6912150Sgabor.dozsa@arm.com virtual ~QTIsaac(void); 7012150Sgabor.dozsa@arm.com 7112150Sgabor.dozsa@arm.com UINT32 rand(void); 7212150Sgabor.dozsa@arm.com virtual void randinit(randctx* ctx, bool bUseSeed); 7312150Sgabor.dozsa@arm.com virtual void srand( 7412150Sgabor.dozsa@arm.com UINT32 a = 0, UINT32 b = 0, UINT32 c = 0, UINT32* s = NULL); 7512150Sgabor.dozsa@arm.com 7612150Sgabor.dozsa@arm.com enum {N = (1<<ALPHA)}; 7712150Sgabor.dozsa@arm.com 7812150Sgabor.dozsa@arm.com protected: 7912150Sgabor.dozsa@arm.com 8012150Sgabor.dozsa@arm.com virtual void isaac(randctx* ctx); 8112150Sgabor.dozsa@arm.com 8212150Sgabor.dozsa@arm.com UINT32 ind(UINT32* mm, UINT32 x); 8312150Sgabor.dozsa@arm.com void rngstep( 8412150Sgabor.dozsa@arm.com UINT32 mix, UINT32& a, UINT32& b, UINT32*& mm, UINT32*& m, 8512150Sgabor.dozsa@arm.com UINT32*& m2, UINT32*& r, UINT32& x, UINT32& y); 8612150Sgabor.dozsa@arm.com virtual void shuffle( 8712150Sgabor.dozsa@arm.com UINT32& a, UINT32& b, UINT32& c, UINT32& d, UINT32& e, UINT32& f, 8812150Sgabor.dozsa@arm.com UINT32& g, UINT32& h); 8912150Sgabor.dozsa@arm.com 9012150Sgabor.dozsa@arm.com private: 9112150Sgabor.dozsa@arm.com randctx m_rc; 9212150Sgabor.dozsa@arm.com}; 9312150Sgabor.dozsa@arm.com 9412150Sgabor.dozsa@arm.com 9512150Sgabor.dozsa@arm.comtemplate<UINT32 ALPHA> 9612150Sgabor.dozsa@arm.comQTIsaac<ALPHA>::QTIsaac(UINT32 a, UINT32 b, UINT32 c) : m_rc() 9712150Sgabor.dozsa@arm.com{ 9812564Sgabeblack@google.com srand(a, b, c); 9912150Sgabor.dozsa@arm.com} 10012150Sgabor.dozsa@arm.com 10112150Sgabor.dozsa@arm.com 10212150Sgabor.dozsa@arm.comtemplate<UINT32 ALPHA> 10312150Sgabor.dozsa@arm.comQTIsaac<ALPHA>::~QTIsaac(void) 10412150Sgabor.dozsa@arm.com{ 10512150Sgabor.dozsa@arm.com // DO NOTHING 10612150Sgabor.dozsa@arm.com} 10712150Sgabor.dozsa@arm.com 10812150Sgabor.dozsa@arm.com 10912150Sgabor.dozsa@arm.comtemplate<UINT32 ALPHA> 11012153Sandreas.sandberg@arm.comvoid QTIsaac<ALPHA>::srand(UINT32 a, UINT32 b, UINT32 c, UINT32* s) 11112150Sgabor.dozsa@arm.com{ 11212150Sgabor.dozsa@arm.com for(int i = 0; i < N; i++) 11312150Sgabor.dozsa@arm.com { 11412150Sgabor.dozsa@arm.com m_rc.randrsl[i] = s != NULL ? s[i] : 0; 11512150Sgabor.dozsa@arm.com } 11612150Sgabor.dozsa@arm.com 11712150Sgabor.dozsa@arm.com m_rc.randa = a; 11812150Sgabor.dozsa@arm.com m_rc.randb = b; 11912150Sgabor.dozsa@arm.com m_rc.randc = c; 12012150Sgabor.dozsa@arm.com 12112150Sgabor.dozsa@arm.com randinit(&m_rc, true); 12212150Sgabor.dozsa@arm.com} 12312150Sgabor.dozsa@arm.com 12412150Sgabor.dozsa@arm.com 12512150Sgabor.dozsa@arm.comtemplate<UINT32 ALPHA> 12612150Sgabor.dozsa@arm.cominline UINT32 QTIsaac<ALPHA>::rand(void) 12712150Sgabor.dozsa@arm.com{ 12812150Sgabor.dozsa@arm.com return 0x7fffffff & (!m_rc.randcnt-- ? 12912150Sgabor.dozsa@arm.com (isaac(&m_rc), m_rc.randcnt=(N-1), m_rc.randrsl[m_rc.randcnt]) : 13012150Sgabor.dozsa@arm.com m_rc.randrsl[m_rc.randcnt]); 13112150Sgabor.dozsa@arm.com} 13212150Sgabor.dozsa@arm.com 13312150Sgabor.dozsa@arm.com 13412150Sgabor.dozsa@arm.comtemplate<UINT32 ALPHA> 13512150Sgabor.dozsa@arm.cominline void QTIsaac<ALPHA>::randinit(randctx* ctx, bool bUseSeed) 13612150Sgabor.dozsa@arm.com{ 13712150Sgabor.dozsa@arm.com UINT32 a,b,c,d,e,f,g,h; 13812150Sgabor.dozsa@arm.com int i; 13912150Sgabor.dozsa@arm.com 14012150Sgabor.dozsa@arm.com a = b = c = d = e = f = g = h = GOLDEN_RATIO; 14112150Sgabor.dozsa@arm.com 14212150Sgabor.dozsa@arm.com UINT32* m = (ctx->randmem); 14312150Sgabor.dozsa@arm.com UINT32* r = (ctx->randrsl); 14412150Sgabor.dozsa@arm.com 14512150Sgabor.dozsa@arm.com if(!bUseSeed) 14612150Sgabor.dozsa@arm.com { 14712150Sgabor.dozsa@arm.com ctx->randa = 0; 14812150Sgabor.dozsa@arm.com ctx->randb = 0; 14912150Sgabor.dozsa@arm.com ctx->randc = 0; 15012150Sgabor.dozsa@arm.com } 15113609Sgiacomo.travaglini@arm.com 15213609Sgiacomo.travaglini@arm.com // scramble it 15313609Sgiacomo.travaglini@arm.com for(i=0; i < 4; ++i) 15413609Sgiacomo.travaglini@arm.com { 15513609Sgiacomo.travaglini@arm.com shuffle(a,b,c,d,e,f,g,h); 15613609Sgiacomo.travaglini@arm.com } 15712150Sgabor.dozsa@arm.com 15812150Sgabor.dozsa@arm.com if(bUseSeed) 15912150Sgabor.dozsa@arm.com { 16012150Sgabor.dozsa@arm.com // initialize using the contents of r[] as the seed 16112150Sgabor.dozsa@arm.com 16212150Sgabor.dozsa@arm.com for(i=0; i < N; i+=8) 16312150Sgabor.dozsa@arm.com { 16412150Sgabor.dozsa@arm.com a+=r[i ]; b+=r[i+1]; c+=r[i+2]; d+=r[i+3]; 16512150Sgabor.dozsa@arm.com e+=r[i+4]; f+=r[i+5]; g+=r[i+6]; h+=r[i+7]; 16612150Sgabor.dozsa@arm.com 16712150Sgabor.dozsa@arm.com shuffle(a,b,c,d,e,f,g,h); 16812150Sgabor.dozsa@arm.com 16912150Sgabor.dozsa@arm.com m[i ]=a; m[i+1]=b; m[i+2]=c; m[i+3]=d; 17012150Sgabor.dozsa@arm.com m[i+4]=e; m[i+5]=f; m[i+6]=g; m[i+7]=h; 17112150Sgabor.dozsa@arm.com } 17212150Sgabor.dozsa@arm.com 17312150Sgabor.dozsa@arm.com //do a second pass to make all of the seed affect all of m 17412150Sgabor.dozsa@arm.com 17512150Sgabor.dozsa@arm.com for(i=0; i < N; i += 8) 17612150Sgabor.dozsa@arm.com { 17712150Sgabor.dozsa@arm.com a+=m[i ]; b+=m[i+1]; c+=m[i+2]; d+=m[i+3]; 17812150Sgabor.dozsa@arm.com e+=m[i+4]; f+=m[i+5]; g+=m[i+6]; h+=m[i+7]; 17912150Sgabor.dozsa@arm.com 18012150Sgabor.dozsa@arm.com shuffle(a,b,c,d,e,f,g,h); 18112564Sgabeblack@google.com 18212150Sgabor.dozsa@arm.com m[i ]=a; m[i+1]=b; m[i+2]=c; m[i+3]=d; 18312150Sgabor.dozsa@arm.com m[i+4]=e; m[i+5]=f; m[i+6]=g; m[i+7]=h; 18412150Sgabor.dozsa@arm.com } 18512150Sgabor.dozsa@arm.com } 18612150Sgabor.dozsa@arm.com else 18712564Sgabeblack@google.com { 18812150Sgabor.dozsa@arm.com // fill in mm[] with messy stuff 18912150Sgabor.dozsa@arm.com 19012564Sgabeblack@google.com shuffle(a,b,c,d,e,f,g,h); 19112150Sgabor.dozsa@arm.com 19212564Sgabeblack@google.com m[i ]=a; m[i+1]=b; m[i+2]=c; m[i+3]=d; 19312150Sgabor.dozsa@arm.com m[i+4]=e; m[i+5]=f; m[i+6]=g; m[i+7]=h; 19412150Sgabor.dozsa@arm.com 19512150Sgabor.dozsa@arm.com } 19612150Sgabor.dozsa@arm.com 19712150Sgabor.dozsa@arm.com isaac(ctx); // fill in the first set of results 19812150Sgabor.dozsa@arm.com ctx->randcnt = N; // prepare to use the first set of results 19912150Sgabor.dozsa@arm.com} 20012150Sgabor.dozsa@arm.com 20112150Sgabor.dozsa@arm.com 20212150Sgabor.dozsa@arm.comtemplate<UINT32 ALPHA> 20312150Sgabor.dozsa@arm.cominline UINT32 QTIsaac<ALPHA>::ind(UINT32* mm, UINT32 x) 20412150Sgabor.dozsa@arm.com{ 20512150Sgabor.dozsa@arm.com return (*(UINT32*)((byte*)(mm) + ((x) & ((N-1)<<2)))); 20612150Sgabor.dozsa@arm.com} 20712150Sgabor.dozsa@arm.com 20812150Sgabor.dozsa@arm.com 20912150Sgabor.dozsa@arm.comtemplate<UINT32 ALPHA> 21012150Sgabor.dozsa@arm.cominline void QTIsaac<ALPHA>::rngstep(UINT32 mix, UINT32& a, UINT32& b, UINT32*& mm, UINT32*& m, UINT32*& m2, UINT32*& r, UINT32& x, UINT32& y) 21112150Sgabor.dozsa@arm.com{ 21212150Sgabor.dozsa@arm.com x = *m; 21312150Sgabor.dozsa@arm.com a = (a^(mix)) + *(m2++); 21412150Sgabor.dozsa@arm.com *(m++) = y = ind(mm,x) + a + b; 21512150Sgabor.dozsa@arm.com *(r++) = b = ind(mm,y>>ALPHA) + x; 21612150Sgabor.dozsa@arm.com} 21712150Sgabor.dozsa@arm.com 21812150Sgabor.dozsa@arm.com 21912150Sgabor.dozsa@arm.comtemplate<UINT32 ALPHA> 22012150Sgabor.dozsa@arm.cominline void QTIsaac<ALPHA>::shuffle(UINT32& a, UINT32& b, UINT32& c, UINT32& d, UINT32& e, UINT32& f, UINT32& g, UINT32& h) 22112150Sgabor.dozsa@arm.com{ 22212150Sgabor.dozsa@arm.com a^=b<<11; d+=a; b+=c; 22312150Sgabor.dozsa@arm.com b^=c>>2; e+=b; c+=d; 22412150Sgabor.dozsa@arm.com c^=d<<8; f+=c; d+=e; 22512150Sgabor.dozsa@arm.com d^=e>>16; g+=d; e+=f; 22612150Sgabor.dozsa@arm.com e^=f<<10; h+=e; f+=g; 22712150Sgabor.dozsa@arm.com f^=g>>4; a+=f; g+=h; 22812150Sgabor.dozsa@arm.com g^=h<<8; b+=g; h+=a; 22912150Sgabor.dozsa@arm.com h^=a>>9; c+=h; a+=b; 23012150Sgabor.dozsa@arm.com} 23112150Sgabor.dozsa@arm.com 23212150Sgabor.dozsa@arm.com 23312150Sgabor.dozsa@arm.comtemplate<UINT32 ALPHA> 23412150Sgabor.dozsa@arm.cominline void QTIsaac<ALPHA>::isaac(randctx* ctx) 23512150Sgabor.dozsa@arm.com{ 23612150Sgabor.dozsa@arm.com UINT32 x,y; 23712150Sgabor.dozsa@arm.com 23812150Sgabor.dozsa@arm.com UINT32* mm = ctx->randmem; 23912150Sgabor.dozsa@arm.com UINT32* r = ctx->randrsl; 24012150Sgabor.dozsa@arm.com 24112150Sgabor.dozsa@arm.com UINT32 a = (ctx->randa); 24212150Sgabor.dozsa@arm.com UINT32 b = (ctx->randb + (++ctx->randc)); 24312150Sgabor.dozsa@arm.com 24412150Sgabor.dozsa@arm.com UINT32* m = mm; 245 UINT32* m2 = (m+(N/2)); 246 UINT32* mend = m2; 247 248 for(; m<mend; ) 249 { 250 rngstep((a<<13), a, b, mm, m, m2, r, x, y); 251 rngstep((a>>6) , a, b, mm, m, m2, r, x, y); 252 rngstep((a<<2) , a, b, mm, m, m2, r, x, y); 253 rngstep((a>>16), a, b, mm, m, m2, r, x, y); 254 } 255 256 m2 = mm; 257 258 for(; m2<mend; ) 259 { 260 rngstep((a<<13), a, b, mm, m, m2, r, x, y); 261 rngstep((a>>6) , a, b, mm, m, m2, r, x, y); 262 rngstep((a<<2) , a, b, mm, m, m2, r, x, y); 263 rngstep((a>>16), a, b, mm, m, m2, r, x, y); 264 } 265 266 ctx->randb = b; 267 ctx->randa = a; 268} 269 270 271#endif // __ISAAC_HPP 272 273