src/isaac64.c

   1 /*Written by Timothy B. Terriberry (tterribe@xiph.org) 1999-2009
   2   CC0 (Public domain) - see http://creativecommons.org/publicdomain/zero/1.0/
   3   for details.
   4   Based on the public domain ISAAC implementation by Robert J. Jenkins Jr.*/
   5
   6 /*
   7  * Changes for NetHack:
   8  *      include config.h;
   9  *      skip rest of file if USE_ISAAC64 isn't defined there;
  10  *      re-do 'inline' handling.
  11  */
  12 #include "config.h"
  13
  14 #ifdef USE_ISAAC64
  15 #include <math.h>
  16 #include <string.h>
  17 #include "isaac64.h"
  18
  19 #define ISAAC64_MASK ((uint64_t)0xFFFFFFFFFFFFFFFFULL)
  20
  21 #if (defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L)
  22 #if !defined(HAS_INLINE)
  23 #define HAS_INLINE
  24 #endif
  25 #else
  26 # if (defined(__GNUC__) && __GNUC__ >= 2 && !defined(inline))
  27 # define inline __inline__
  28 # endif
  29 #endif
  30 #if !defined(HAS_INLINE) && !defined(inline)
  31 #define inline /*empty*/
  32 #endif
  33
  34 /* Extract ISAAC64_SZ_LOG bits (starting at bit 3). */
  35 static inline uint32_t lower_bits(uint64_t x)
  36 {
  37         return (x & ((ISAAC64_SZ-1) << 3)) >>3;
  38 }
  39
  40 /* Extract next ISAAC64_SZ_LOG bits (starting at bit ISAAC64_SZ_LOG+2). */
  41 static inline uint32_t upper_bits(uint64_t y)
  42 {
  43         return (y >> (ISAAC64_SZ_LOG+3)) & (ISAAC64_SZ-1);
  44 }
  45
  46 static void isaac64_update(isaac64_ctx *_ctx){
  47   uint64_t *m;
  48   uint64_t *r;
  49   uint64_t  a;
  50   uint64_t  b;
  51   uint64_t  x;
  52   uint64_t  y;
  53   int       i;
  54   m=_ctx->m;
  55   r=_ctx->r;
  56   a=_ctx->a;
  57   b=_ctx->b+(++_ctx->c);
  58   for(i=0;i<ISAAC64_SZ/2;i++){
  59     x=m[i];
  60     a=~(a^a<<21)+m[i+ISAAC64_SZ/2];
  61     m[i]=y=m[lower_bits(x)]+a+b;
  62     r[i]=b=m[upper_bits(y)]+x;
  63     x=m[++i];
  64     a=(a^a>>5)+m[i+ISAAC64_SZ/2];
  65     m[i]=y=m[lower_bits(x)]+a+b;
  66     r[i]=b=m[upper_bits(y)]+x;
  67     x=m[++i];
  68     a=(a^a<<12)+m[i+ISAAC64_SZ/2];
  69     m[i]=y=m[lower_bits(x)]+a+b;
  70     r[i]=b=m[upper_bits(y)]+x;
  71     x=m[++i];
  72     a=(a^a>>33)+m[i+ISAAC64_SZ/2];
  73     m[i]=y=m[lower_bits(x)]+a+b;
  74     r[i]=b=m[upper_bits(y)]+x;
  75   }
  76   for(i=ISAAC64_SZ/2;i<ISAAC64_SZ;i++){
  77     x=m[i];
  78     a=~(a^a<<21)+m[i-ISAAC64_SZ/2];
  79     m[i]=y=m[lower_bits(x)]+a+b;
  80     r[i]=b=m[upper_bits(y)]+x;
  81     x=m[++i];
  82     a=(a^a>>5)+m[i-ISAAC64_SZ/2];
  83     m[i]=y=m[lower_bits(x)]+a+b;
  84     r[i]=b=m[upper_bits(y)]+x;
  85     x=m[++i];
  86     a=(a^a<<12)+m[i-ISAAC64_SZ/2];
  87     m[i]=y=m[lower_bits(x)]+a+b;
  88     r[i]=b=m[upper_bits(y)]+x;
  89     x=m[++i];
  90     a=(a^a>>33)+m[i-ISAAC64_SZ/2];
  91     m[i]=y=m[lower_bits(x)]+a+b;
  92     r[i]=b=m[upper_bits(y)]+x;
  93   }
  94   _ctx->b=b;
  95   _ctx->a=a;
  96   _ctx->n=ISAAC64_SZ;
  97 }
  98
  99 static void isaac64_mix(uint64_t _x[8]){
 100   static const unsigned char SHIFT[8]={9,9,23,15,14,20,17,14};
 101   int i;
 102   for(i=0;i<8;i++){
 103     _x[i]-=_x[(i+4)&7];
 104     _x[(i+5)&7]^=_x[(i+7)&7]>>SHIFT[i];
 105     _x[(i+7)&7]+=_x[i];
 106     i++;
 107     _x[i]-=_x[(i+4)&7];
 108     _x[(i+5)&7]^=_x[(i+7)&7]<<SHIFT[i];
 109     _x[(i+7)&7]+=_x[i];
 110   }
 111 }
 112
 113
 114 void isaac64_init(isaac64_ctx *_ctx,const unsigned char *_seed,int _nseed){
 115   _ctx->a=_ctx->b=_ctx->c=0;
 116   memset(_ctx->r,0,sizeof(_ctx->r));
 117   isaac64_reseed(_ctx,_seed,_nseed);
 118 }
 119
 120 void isaac64_reseed(isaac64_ctx *_ctx,const unsigned char *_seed,int _nseed){
 121   uint64_t *m;
 122   uint64_t *r;
 123   uint64_t  x[8];
 124   int       i;
 125   int       j;
 126   m=_ctx->m;
 127   r=_ctx->r;
 128   if(_nseed>ISAAC64_SEED_SZ_MAX)_nseed=ISAAC64_SEED_SZ_MAX;
 129   for(i=0;i<_nseed>>3;i++){
 130     r[i]^=(uint64_t)_seed[i<<3|7]<<56|(uint64_t)_seed[i<<3|6]<<48|
 131      (uint64_t)_seed[i<<3|5]<<40|(uint64_t)_seed[i<<3|4]<<32|
 132      (uint64_t)_seed[i<<3|3]<<24|(uint64_t)_seed[i<<3|2]<<16|
 133      (uint64_t)_seed[i<<3|1]<<8|_seed[i<<3];
 134   }
 135   _nseed-=i<<3;
 136   if(_nseed>0){
 137     uint64_t ri;
 138     ri=_seed[i<<3];
 139     for(j=1;j<_nseed;j++)ri|=(uint64_t)_seed[i<<3|j]<<(j<<3);
 140     r[i++]^=ri;
 141   }
 142   x[0]=x[1]=x[2]=x[3]=x[4]=x[5]=x[6]=x[7]=(uint64_t)0x9E3779B97F4A7C13ULL;
 143   for(i=0;i<4;i++)isaac64_mix(x);
 144   for(i=0;i<ISAAC64_SZ;i+=8){
 145     for(j=0;j<8;j++)x[j]+=r[i+j];
 146     isaac64_mix(x);
 147     memcpy(m+i,x,sizeof(x));
 148   }
 149   for(i=0;i<ISAAC64_SZ;i+=8){
 150     for(j=0;j<8;j++)x[j]+=m[i+j];
 151     isaac64_mix(x);
 152     memcpy(m+i,x,sizeof(x));
 153   }
 154   isaac64_update(_ctx);
 155 }
 156
 157 uint64_t isaac64_next_uint64(isaac64_ctx *_ctx){
 158   if(!_ctx->n)isaac64_update(_ctx);
 159   return _ctx->r[--_ctx->n];
 160 }
 161
 162 uint64_t isaac64_next_uint(isaac64_ctx *_ctx,uint64_t _n){
 163   uint64_t r;
 164   uint64_t v;
 165   uint64_t d;
 166   do{
 167     r=isaac64_next_uint64(_ctx);
 168     v=r%_n;
 169     d=r-v;
 170   }
 171   while(((d+_n-1)&ISAAC64_MASK)<d);
 172   return v;
 173 }
 174 #endif /* USE_ISAAC64 */
 175
 176 /*isaac64.c*/