BeRTOS
isaac.c
Go to the documentation of this file.
00001 
00038 /*
00039 ------------------------------------------------------------------------------
00040 rand.c: By Bob Jenkins.  My random number generator, ISAAC.  Public Domain.
00041 MODIFIED:
00042   960327: Creation (addition of randinit, really)
00043   970719: use context, not global variables, for internal state
00044   980324: added main (ifdef'ed out), also rearranged randinit()
00045   010626: Note that this is public domain
00046 ------------------------------------------------------------------------------
00047 */
00048 
00049 #include "isaac.h"
00050 #include <sec/prng.h>
00051 #include <sec/util.h>
00052 #include <cfg/compiler.h>
00053 #include <cfg/macros.h>
00054 #include <string.h>
00055 
00056 typedef uint32_t ub4;
00057 typedef uint16_t ub2;
00058 typedef uint8_t ub1;
00059 
00060 #define ind(mm,x)  (*(ub4 *)((size_t)(mm) + ((x) & ((CONFIG_ISAAC_RANDSIZ-1)<<2))))
00061 #define rngstep(mix,a,b,mm,m,m2,r,x) \
00062 { \
00063   x = *m;  \
00064   a = (a^(mix)) + *(m2++); \
00065   *(m++) = y = ind(mm,x) + a + b; \
00066   *(r++) = b = ind(mm,y>>CONFIG_ISAAC_RANDSIZL) + x; \
00067 }
00068 
00069 static void isaac(IsaacContext *ctx)
00070 {
00071     register ub4 a,b,x,y,*m,*mm,*m2,*r,*mend;
00072     mm=ctx->randmem; r=ctx->randrsl;
00073     a = ctx->randa; b = ctx->randb + (++ctx->randc);
00074     for (m = mm, mend = m2 = m+(CONFIG_ISAAC_RANDSIZ/2); m<mend; )
00075     {
00076         rngstep( a<<13, a, b, mm, m, m2, r, x);
00077         rngstep( a>>6 , a, b, mm, m, m2, r, x);
00078         rngstep( a<<2 , a, b, mm, m, m2, r, x);
00079         rngstep( a>>16, a, b, mm, m, m2, r, x);
00080     }
00081     for (m2 = mm; m2<mend; )
00082     {
00083         rngstep( a<<13, a, b, mm, m, m2, r, x);
00084         rngstep( a>>6 , a, b, mm, m, m2, r, x);
00085         rngstep( a<<2 , a, b, mm, m, m2, r, x);
00086         rngstep( a>>16, a, b, mm, m, m2, r, x);
00087     }
00088     ctx->randb = b; ctx->randa = a;
00089 }
00090 
00091 
00092 #define mix(a,b,c,d,e,f,g,h) \
00093 { \
00094    a^=b<<11; d+=a; b+=c; \
00095    b^=c>>2;  e+=b; c+=d; \
00096    c^=d<<8;  f+=c; d+=e; \
00097    d^=e>>16; g+=d; e+=f; \
00098    e^=f<<10; h+=e; f+=g; \
00099    f^=g>>4;  a+=f; g+=h; \
00100    g^=h<<8;  b+=g; h+=a; \
00101    h^=a>>9;  c+=h; a+=b; \
00102 }
00103 
00104 static void isaac_reseed(PRNG *ctx_, const uint8_t *seed)
00105 {
00106     IsaacContext *ctx = (IsaacContext *)ctx_;
00107     int i;
00108     ub4 a,b,c,d,e,f,g,h;
00109     ub4 *m,*r;
00110 
00111     // XOR the new seed over the current state, so to depend on
00112     // the previously-generated output.
00113     xor_block(ctx->randrsl, ctx->randrsl, seed, sizeof(ctx->randrsl));
00114 
00115     ctx->randa = ctx->randb = ctx->randc = 0;
00116     m=ctx->randmem;
00117     r=ctx->randrsl;
00118     a=b=c=d=e=f=g=h=0x9e3779b9;  /* the golden ratio */
00119 
00120     for (i=0; i<4; ++i)          /* scramble it */
00121     {
00122         mix(a,b,c,d,e,f,g,h);
00123     }
00124 
00125     /* initialize using the contents of r[] as the seed */
00126     for (i=0; i<CONFIG_ISAAC_RANDSIZ; i+=8)
00127     {
00128         a+=r[i  ]; b+=r[i+1]; c+=r[i+2]; d+=r[i+3];
00129         e+=r[i+4]; f+=r[i+5]; g+=r[i+6]; h+=r[i+7];
00130         mix(a,b,c,d,e,f,g,h);
00131         m[i  ]=a; m[i+1]=b; m[i+2]=c; m[i+3]=d;
00132         m[i+4]=e; m[i+5]=f; m[i+6]=g; m[i+7]=h;
00133     }
00134     /* do a second pass to make all of the seed affect all of m */
00135     for (i=0; i<CONFIG_ISAAC_RANDSIZ; i+=8)
00136     {
00137         a+=m[i  ]; b+=m[i+1]; c+=m[i+2]; d+=m[i+3];
00138         e+=m[i+4]; f+=m[i+5]; g+=m[i+6]; h+=m[i+7];
00139         mix(a,b,c,d,e,f,g,h);
00140         m[i  ]=a; m[i+1]=b; m[i+2]=c; m[i+3]=d;
00141         m[i+4]=e; m[i+5]=f; m[i+6]=g; m[i+7]=h;
00142     }
00143 }
00144 
00145 static void isaac_generate(PRNG *ctx_, uint8_t *data, size_t len)
00146 {
00147     IsaacContext *ctx = (IsaacContext *)ctx_;
00148 
00149     STATIC_ASSERT(sizeof(ctx->randrsl) == CONFIG_ISAAC_RANDSIZ*4);
00150 
00151     while (len)
00152     {
00153         ASSERT(ctx->randcnt <= CONFIG_ISAAC_RANDSIZ*4);
00154 
00155         if (ctx->randcnt == CONFIG_ISAAC_RANDSIZ*4)
00156         {
00157             isaac(ctx);
00158             ctx->randcnt = 0;
00159         }
00160 
00161         size_t L = MIN(len, CONFIG_ISAAC_RANDSIZ*4 - (size_t)ctx->randcnt);
00162         memcpy(data, (uint8_t*)ctx->randrsl + ctx->randcnt, L);
00163         data += L;
00164         ctx->randcnt += L;
00165         len -= L;
00166     }
00167 }
00168 
00169 
00170 /**********************************************************************/
00171 
00172 void isaac_init(IsaacContext *ctx)
00173 {
00174     ctx->prng.reseed = isaac_reseed;
00175     ctx->prng.generate = isaac_generate;
00176     ctx->prng.seed_len = sizeof(ctx->randrsl);
00177     ctx->prng.seeded = 0;
00178 
00179     ctx->randcnt = CONFIG_ISAAC_RANDSIZ*4;
00180     memset(ctx->randrsl, 0, sizeof(ctx->randrsl));
00181 }
00182 
00183 
00184 
00185 
00186 #ifdef NEVER
00187 int main()
00188 {
00189   ub4 i,j;
00190   randctx ctx;
00191   ctx.randa=ctx.randb=ctx.randc=(ub4)0;
00192   for (i=0; i<256; ++i) ctx.randrsl[i]=(ub4)0;
00193   randinit(&ctx, TRUE);
00194   for (i=0; i<2; ++i)
00195   {
00196     isaac(&ctx);
00197     for (j=0; j<256; ++j)
00198     {
00199       printf("%.8lx",ctx.randrsl[j]);
00200       if ((j&7)==7) printf("\n");
00201     }
00202   }
00203 }
00204 #endif