/*A prng without crypto credentials.
Based on SHA-1 with some attention to efficiency.

C version:
prngS gg(long long);
This returns an opaque block which retains
the state of a prng (Pseudo Random Number Generator).
The initial state is a function of the argument.

int Rand(prngS *, int n); // 0< n <= 32
This returns an n bit random number based on the
state of the prngS, which is updated.
The cost is proportional to n.

The abstracted state is indeed a 160 bit SHA block
which serves as both input and output to the basic
SHA computation. The other 64 bytes are the
original 64 bit seed placed at the right end
of the initial 64 byte input.
Subsequent 64 byte inputs are all zero.

"Rand" returns the next n bits of the most recent
160 bit result, which is regenerated when exhausted.

This fails on several counts as a one time pad crypto scheme.
I do this because I have spent too much time recently
tracking bugs to poor quality RNG's.*/

typedef unsigned int u32;
typedef u32 fx(u32, u32, u32);
static void init(u32 H[5]){H[0]=0x67452301;
  H[1]=0xEFCDAB89; H[2]=0x98BADCFE;
  H[3]=0x10325476; H[4]=0xC3D2E1F0;}
static u32 f0(u32 b, u32 c, u32 d) {return (b & c) | ((~ b) & d);}
static u32 f1(u32 b, u32 c, u32 d) {return b ^ c ^ d;}
static u32 f2(u32 b, u32 c, u32 d) {return b&c | b&d | c&d;}
static u32 Rl(u32 X, int n){return (X << n) | (X >> (32-n));}
static void doBlock(u32 W[16], u32 H[5])
{ u32 w[80]; u32 a=H[0], b=H[1], c=H[2], d=H[3], e=H[4];
  static void ts(fx* f, u32 k, int st)
    { int t; for(t=0; t<20; ++t)
      {u32 tmp=Rl(a,5) + f(b,c,d) + e + w[st++] + k;
       e = d; d = c; c = Rl(b, 30); b = a; a = tmp;}}
  { int j; for(j=0; j<16; ++j) w[j]=W[j];}
  { int t; for(t=16; t<80; ++t)
    w[t] = Rl(w[t-3]^w[t-8]^w[t-14]^w[t-16], 1);}
  ts(f0, 0x5A827999, 0); ts(f1, 0x6ED9EBA1, 20);
  ts(f2, 0x8F1BBCDC, 40); ts(f1, 0xCA62C1D6, 60);
  H[0] += a; H[1] += b; H[2] += c; H[3] += d; H[4] += e;
}

typedef struct{u32 st[5]; int bc;} prngS; // Don't peek!

int Rand(prngS *, int n);
prngS gg(long long); // Belongs in header

prngS gg(long long x){int str[16]; prngS s;
   init(s.st);
   {int j=14; while(j--) str[j]=0;}
   *(long long *)&str[14] = x;
   doBlock(str, s.st);
   s.bc = 160; // Start out full.
   return s;}


// 0<= a <32 & 0 < n <= 32
static int ff(u32 p0, u32 p1, int a, int n){
  return (a+n>32?(p0<< ((a+n)-32))|(p1 >> (64-(a+n)))
                :p0 >> (32 - (a+n))) & ((1<<n)-1);}

int Rand(prngS* s, int n){
  if(s->bc < n) {int p0 = s->st[4];
  int v = 32-s->bc;
  {int z[16]; int j = 16; while(j--) z[j]=0;
     doBlock(z, s->st);} s->bc += 160-n;
     return ff(p0, s->st[0], v, n);}
  {int oc = 160 - s->bc, *x = s->st + (oc >> 5);
   s->bc -= n;
   return ff(*x, *(x+1), oc&31 , n);}}

#if 0
#include <stdio.h>
int main(){prngS q = gg(5);
double sq(double x){return x*x;}
int const K = 4, s2 = 10000000;
int nc[1<<K]; {int j=1<<K; while(j--) nc[j]=0;}
{int j=s2; while(j--) ++nc[Rand(&q, K)];}
{int j = 1<<K; double s = 0;
while(j--) {printf("%d ", nc[j]); s += sq(nc[j]-(s2>>K));}
 printf("\n%d, %16.8e\n", s2, s);}}
// s should usually be less than s2.
// K, s2 and the argument to gg can be varied for more tests.
#endif