isaac.h revision 12855
12568SN/A#ifndef __ISAAC_HPP 22568SN/A#define __ISAAC_HPP 32568SN/A 42568SN/A 52568SN/A/* 62568SN/A 72568SN/A C++ TEMPLATE VERSION OF Robert J. Jenkins Jr.'s 82568SN/A ISAAC Random Number Generator. 92568SN/A 102568SN/A Ported from vanilla C to to template C++ class 112568SN/A by Quinn Tyler Jackson on 16-23 July 1998. 122568SN/A 132568SN/A quinn@qtj.net 142568SN/A 152568SN/A The function for the expected period of this 162568SN/A random number generator, according to Jenkins is: 172568SN/A 182568SN/A f(a,b) = 2**((a+b*(3+2^^a)-1) 192568SN/A 202568SN/A (where a is ALPHA and b is bitwidth) 212568SN/A 222568SN/A So, for a bitwidth of 32 and an ALPHA of 8, 232568SN/A the expected period of ISAAC is: 242568SN/A 252568SN/A 2^^(8+32*(3+2^^8)-1) = 2^^8295 262568SN/A 272568SN/A Jackson has been able to run implementations 282665Ssaidi@eecs.umich.edu with an ALPHA as high as 16, or 292665Ssaidi@eecs.umich.edu 302665Ssaidi@eecs.umich.edu 2^^2097263 312568SN/A 322568SN/A*/ 332568SN/A 342982Sstever@eecs.umich.edu 352982Sstever@eecs.umich.edutypedef unsigned int UINT32; 362568SN/Aconst UINT32 GOLDEN_RATIO = UINT32(0x9e3779b9); 372568SN/A 382643Sstever@eecs.umich.edu 392568SN/Atemplate <UINT32 ALPHA = (8)> 402568SN/Aclass QTIsaac 412568SN/A{ 424762Snate@binkert.org public: 432568SN/A 442643Sstever@eecs.umich.edu typedef unsigned char byte; 452643Sstever@eecs.umich.edu 464435Ssaidi@eecs.umich.edu struct randctx 474435Ssaidi@eecs.umich.edu { 482643Sstever@eecs.umich.edu randctx(void) 494435Ssaidi@eecs.umich.edu { 504435Ssaidi@eecs.umich.edu randrsl = new UINT32[N]; 514435Ssaidi@eecs.umich.edu randmem = new UINT32[N]; 522643Sstever@eecs.umich.edu } 532643Sstever@eecs.umich.edu 542643Sstever@eecs.umich.edu ~randctx(void) 554435Ssaidi@eecs.umich.edu { 564435Ssaidi@eecs.umich.edu delete [] randrsl; 574435Ssaidi@eecs.umich.edu delete [] randmem; 584435Ssaidi@eecs.umich.edu } 594435Ssaidi@eecs.umich.edu 604435Ssaidi@eecs.umich.edu UINT32 randcnt; 614435Ssaidi@eecs.umich.edu UINT32* randrsl; 622643Sstever@eecs.umich.edu UINT32* randmem; 634432Ssaidi@eecs.umich.edu UINT32 randa; 644432Ssaidi@eecs.umich.edu UINT32 randb; 652643Sstever@eecs.umich.edu UINT32 randc; 662643Sstever@eecs.umich.edu }; 672643Sstever@eecs.umich.edu 682738Sstever@eecs.umich.edu QTIsaac(UINT32 a = 0, UINT32 b = 0, UINT32 c = 0); 692643Sstever@eecs.umich.edu virtual ~QTIsaac(void); 702643Sstever@eecs.umich.edu 712643Sstever@eecs.umich.edu UINT32 rand(void); 722643Sstever@eecs.umich.edu virtual void randinit(randctx* ctx, bool bUseSeed); 732643Sstever@eecs.umich.edu virtual void srand( 742643Sstever@eecs.umich.edu UINT32 a = 0, UINT32 b = 0, UINT32 c = 0, UINT32* s = NULL); 752643Sstever@eecs.umich.edu 762643Sstever@eecs.umich.edu enum {N = (1<<ALPHA)}; 772643Sstever@eecs.umich.edu 782643Sstever@eecs.umich.edu protected: 792643Sstever@eecs.umich.edu 802643Sstever@eecs.umich.edu virtual void isaac(randctx* ctx); 812643Sstever@eecs.umich.edu 822643Sstever@eecs.umich.edu UINT32 ind(UINT32* mm, UINT32 x); 832643Sstever@eecs.umich.edu void rngstep( 842643Sstever@eecs.umich.edu UINT32 mix, UINT32& a, UINT32& b, UINT32*& mm, UINT32*& m, 852568SN/A UINT32*& m2, UINT32*& r, UINT32& x, UINT32& y); 862568SN/A virtual void shuffle( 872568SN/A UINT32& a, UINT32& b, UINT32& c, UINT32& d, UINT32& e, UINT32& f, 882568SN/A UINT32& g, UINT32& h); 892643Sstever@eecs.umich.edu 904432Ssaidi@eecs.umich.edu private: 914432Ssaidi@eecs.umich.edu randctx m_rc; 924432Ssaidi@eecs.umich.edu}; 934432Ssaidi@eecs.umich.edu 942568SN/A 952568SN/Atemplate<UINT32 ALPHA> 964433Ssaidi@eecs.umich.eduQTIsaac<ALPHA>::QTIsaac(UINT32 a, UINT32 b, UINT32 c) : m_rc() 974435Ssaidi@eecs.umich.edu{ 984433Ssaidi@eecs.umich.edu srand(a, b, c); 994435Ssaidi@eecs.umich.edu} 1004435Ssaidi@eecs.umich.edu 1014435Ssaidi@eecs.umich.edu 1024435Ssaidi@eecs.umich.edutemplate<UINT32 ALPHA> 1034435Ssaidi@eecs.umich.eduQTIsaac<ALPHA>::~QTIsaac(void) 1044435Ssaidi@eecs.umich.edu{ 1054435Ssaidi@eecs.umich.edu // DO NOTHING 1064435Ssaidi@eecs.umich.edu} 1074435Ssaidi@eecs.umich.edu 1084433Ssaidi@eecs.umich.edu 1092568SN/Atemplate<UINT32 ALPHA> 1102643Sstever@eecs.umich.eduvoid QTIsaac<ALPHA>::srand(UINT32 a, UINT32 b, UINT32 c, UINT32* s) 1112568SN/A{ 1122568SN/A for(int i = 0; i < N; i++) 1133349Sbinkertn@umich.edu { 1142568SN/A m_rc.randrsl[i] = s != NULL ? s[i] : 0; 1154433Ssaidi@eecs.umich.edu } 1164433Ssaidi@eecs.umich.edu 1174433Ssaidi@eecs.umich.edu m_rc.randa = a; 1184433Ssaidi@eecs.umich.edu m_rc.randb = b; 1194433Ssaidi@eecs.umich.edu m_rc.randc = c; 1203662Srdreslin@umich.edu 1212643Sstever@eecs.umich.edu randinit(&m_rc, true); 1224450Ssaidi@eecs.umich.edu} 1234450Ssaidi@eecs.umich.edu 1244450Ssaidi@eecs.umich.edu 1254450Ssaidi@eecs.umich.edutemplate<UINT32 ALPHA> 1264450Ssaidi@eecs.umich.eduinline UINT32 QTIsaac<ALPHA>::rand(void) 1274450Ssaidi@eecs.umich.edu{ 1284450Ssaidi@eecs.umich.edu return 0x7fffffff & (!m_rc.randcnt-- ? 1294450Ssaidi@eecs.umich.edu (isaac(&m_rc), m_rc.randcnt=(N-1), m_rc.randrsl[m_rc.randcnt]) : 1304433Ssaidi@eecs.umich.edu m_rc.randrsl[m_rc.randcnt]); 1314433Ssaidi@eecs.umich.edu} 1324433Ssaidi@eecs.umich.edu 1333662Srdreslin@umich.edu 1344433Ssaidi@eecs.umich.edutemplate<UINT32 ALPHA> 1354433Ssaidi@eecs.umich.eduinline void QTIsaac<ALPHA>::randinit(randctx* ctx, bool bUseSeed) 1364435Ssaidi@eecs.umich.edu{ 1374433Ssaidi@eecs.umich.edu UINT32 a,b,c,d,e,f,g,h; 1384433Ssaidi@eecs.umich.edu int i; 1394433Ssaidi@eecs.umich.edu 1404433Ssaidi@eecs.umich.edu a = b = c = d = e = f = g = h = GOLDEN_RATIO; 1414433Ssaidi@eecs.umich.edu 1424433Ssaidi@eecs.umich.edu UINT32* m = (ctx->randmem); 1434433Ssaidi@eecs.umich.edu UINT32* r = (ctx->randrsl); 1444433Ssaidi@eecs.umich.edu 1454433Ssaidi@eecs.umich.edu if(!bUseSeed) 1464433Ssaidi@eecs.umich.edu { 1474433Ssaidi@eecs.umich.edu ctx->randa = 0; 1484433Ssaidi@eecs.umich.edu ctx->randb = 0; 1494433Ssaidi@eecs.umich.edu ctx->randc = 0; 1502657Ssaidi@eecs.umich.edu } 1512657Ssaidi@eecs.umich.edu 1524433Ssaidi@eecs.umich.edu // scramble it 1534433Ssaidi@eecs.umich.edu for(i=0; i < 4; ++i) 1544433Ssaidi@eecs.umich.edu { 1554433Ssaidi@eecs.umich.edu shuffle(a,b,c,d,e,f,g,h); 1564433Ssaidi@eecs.umich.edu } 1574433Ssaidi@eecs.umich.edu 1582657Ssaidi@eecs.umich.edu if(bUseSeed) 1594433Ssaidi@eecs.umich.edu { 1604435Ssaidi@eecs.umich.edu // initialize using the contents of r[] as the seed 1614433Ssaidi@eecs.umich.edu 1624435Ssaidi@eecs.umich.edu for(i=0; i < N; i+=8) 1634435Ssaidi@eecs.umich.edu { 1644433Ssaidi@eecs.umich.edu a+=r[i ]; b+=r[i+1]; c+=r[i+2]; d+=r[i+3]; 1654435Ssaidi@eecs.umich.edu e+=r[i+4]; f+=r[i+5]; g+=r[i+6]; h+=r[i+7]; 1664433Ssaidi@eecs.umich.edu 1674435Ssaidi@eecs.umich.edu shuffle(a,b,c,d,e,f,g,h); 1684435Ssaidi@eecs.umich.edu 1694433Ssaidi@eecs.umich.edu m[i ]=a; m[i+1]=b; m[i+2]=c; m[i+3]=d; 1704435Ssaidi@eecs.umich.edu m[i+4]=e; m[i+5]=f; m[i+6]=g; m[i+7]=h; 1714435Ssaidi@eecs.umich.edu } 1724435Ssaidi@eecs.umich.edu 1734435Ssaidi@eecs.umich.edu //do a second pass to make all of the seed affect all of m 1744435Ssaidi@eecs.umich.edu 1754435Ssaidi@eecs.umich.edu for(i=0; i < N; i += 8) 1764435Ssaidi@eecs.umich.edu { 1774435Ssaidi@eecs.umich.edu a+=m[i ]; b+=m[i+1]; c+=m[i+2]; d+=m[i+3]; 1784435Ssaidi@eecs.umich.edu e+=m[i+4]; f+=m[i+5]; g+=m[i+6]; h+=m[i+7]; 1794435Ssaidi@eecs.umich.edu 1804435Ssaidi@eecs.umich.edu shuffle(a,b,c,d,e,f,g,h); 1814435Ssaidi@eecs.umich.edu 1824435Ssaidi@eecs.umich.edu m[i ]=a; m[i+1]=b; m[i+2]=c; m[i+3]=d; 1834435Ssaidi@eecs.umich.edu m[i+4]=e; m[i+5]=f; m[i+6]=g; m[i+7]=h; 1844435Ssaidi@eecs.umich.edu } 1854435Ssaidi@eecs.umich.edu } 1864435Ssaidi@eecs.umich.edu else 1874435Ssaidi@eecs.umich.edu { 1884435Ssaidi@eecs.umich.edu // fill in mm[] with messy stuff 1894435Ssaidi@eecs.umich.edu 1904435Ssaidi@eecs.umich.edu shuffle(a,b,c,d,e,f,g,h); 1914435Ssaidi@eecs.umich.edu 1924435Ssaidi@eecs.umich.edu m[i ]=a; m[i+1]=b; m[i+2]=c; m[i+3]=d; 1934435Ssaidi@eecs.umich.edu m[i+4]=e; m[i+5]=f; m[i+6]=g; m[i+7]=h; 1944435Ssaidi@eecs.umich.edu 1954433Ssaidi@eecs.umich.edu } 1964433Ssaidi@eecs.umich.edu 1974433Ssaidi@eecs.umich.edu isaac(ctx); // fill in the first set of results 1984433Ssaidi@eecs.umich.edu ctx->randcnt = N; // prepare to use the first set of results 1993349Sbinkertn@umich.edu} 2002657Ssaidi@eecs.umich.edu 2014450Ssaidi@eecs.umich.edu 2022643Sstever@eecs.umich.edutemplate<UINT32 ALPHA> 2032643Sstever@eecs.umich.eduinline UINT32 QTIsaac<ALPHA>::ind(UINT32* mm, UINT32 x) 2042643Sstever@eecs.umich.edu{ 2052643Sstever@eecs.umich.edu return (*(UINT32*)((byte*)(mm) + ((x) & ((N-1)<<2)))); 2062643Sstever@eecs.umich.edu} 2072643Sstever@eecs.umich.edu 2082643Sstever@eecs.umich.edu 2092643Sstever@eecs.umich.edutemplate<UINT32 ALPHA> 2104433Ssaidi@eecs.umich.eduinline void QTIsaac<ALPHA>::rngstep(UINT32 mix, UINT32& a, UINT32& b, UINT32*& mm, UINT32*& m, UINT32*& m2, UINT32*& r, UINT32& x, UINT32& y) 2114450Ssaidi@eecs.umich.edu{ 2124450Ssaidi@eecs.umich.edu x = *m; 2134450Ssaidi@eecs.umich.edu a = (a^(mix)) + *(m2++); 2144433Ssaidi@eecs.umich.edu *(m++) = y = ind(mm,x) + a + b; 2154433Ssaidi@eecs.umich.edu *(r++) = b = ind(mm,y>>ALPHA) + x; 2164739Sstever@eecs.umich.edu} 2172643Sstever@eecs.umich.edu 2182643Sstever@eecs.umich.edu 2192643Sstever@eecs.umich.edutemplate<UINT32 ALPHA> 2204450Ssaidi@eecs.umich.eduinline void QTIsaac<ALPHA>::shuffle(UINT32& a, UINT32& b, UINT32& c, UINT32& d, UINT32& e, UINT32& f, UINT32& g, UINT32& h) 2214450Ssaidi@eecs.umich.edu{ 2224450Ssaidi@eecs.umich.edu a^=b<<11; d+=a; b+=c; 2234450Ssaidi@eecs.umich.edu b^=c>>2; e+=b; c+=d; 2244450Ssaidi@eecs.umich.edu c^=d<<8; f+=c; d+=e; 2254450Ssaidi@eecs.umich.edu d^=e>>16; g+=d; e+=f; 2264450Ssaidi@eecs.umich.edu e^=f<<10; h+=e; f+=g; 2272643Sstever@eecs.umich.edu f^=g>>4; a+=f; g+=h; 2282643Sstever@eecs.umich.edu g^=h<<8; b+=g; h+=a; 2292643Sstever@eecs.umich.edu h^=a>>9; c+=h; a+=b; 2302643Sstever@eecs.umich.edu} 2312643Sstever@eecs.umich.edu 2322643Sstever@eecs.umich.edu 2332643Sstever@eecs.umich.edutemplate<UINT32 ALPHA> 2342643Sstever@eecs.umich.eduinline void QTIsaac<ALPHA>::isaac(randctx* ctx) 2352643Sstever@eecs.umich.edu{ 2362568SN/A UINT32 x,y; 2372643Sstever@eecs.umich.edu 2382568SN/A UINT32* mm = ctx->randmem; 2392568SN/A UINT32* r = ctx->randrsl; 2402568SN/A 2412643Sstever@eecs.umich.edu UINT32 a = (ctx->randa); 2422568SN/A UINT32 b = (ctx->randb + (++ctx->randc)); 2432643Sstever@eecs.umich.edu 2442568SN/A UINT32* m = mm; 2452643Sstever@eecs.umich.edu UINT32* m2 = (m+(N/2)); 2462643Sstever@eecs.umich.edu UINT32* mend = m2; 2472643Sstever@eecs.umich.edu 2482643Sstever@eecs.umich.edu for(; m<mend; ) 2493349Sbinkertn@umich.edu { 2502643Sstever@eecs.umich.edu rngstep((a<<13), a, b, mm, m, m2, r, x, y); 2514432Ssaidi@eecs.umich.edu rngstep((a>>6) , a, b, mm, m, m2, r, x, y); 2524432Ssaidi@eecs.umich.edu rngstep((a<<2) , a, b, mm, m, m2, r, x, y); 2534454Ssaidi@eecs.umich.edu rngstep((a>>16), a, b, mm, m, m2, r, x, y); 2544432Ssaidi@eecs.umich.edu } 2554454Ssaidi@eecs.umich.edu 2564454Ssaidi@eecs.umich.edu m2 = mm; 2574454Ssaidi@eecs.umich.edu 2584454Ssaidi@eecs.umich.edu for(; m2<mend; ) 2594454Ssaidi@eecs.umich.edu { 2604454Ssaidi@eecs.umich.edu rngstep((a<<13), a, b, mm, m, m2, r, x, y); 2614454Ssaidi@eecs.umich.edu rngstep((a>>6) , a, b, mm, m, m2, r, x, y); 2624432Ssaidi@eecs.umich.edu rngstep((a<<2) , a, b, mm, m, m2, r, x, y); 2634432Ssaidi@eecs.umich.edu rngstep((a>>16), a, b, mm, m, m2, r, x, y); 2642643Sstever@eecs.umich.edu } 2652643Sstever@eecs.umich.edu 2662643Sstever@eecs.umich.edu ctx->randb = b; 2674450Ssaidi@eecs.umich.edu ctx->randa = a; 2684450Ssaidi@eecs.umich.edu} 2694432Ssaidi@eecs.umich.edu 2702643Sstever@eecs.umich.edu 2712643Sstever@eecs.umich.edu#endif // __ISAAC_HPP 2722643Sstever@eecs.umich.edu 2732643Sstever@eecs.umich.edu