#include <stdio.h>
#include <stdint.h>
#include <windows.h>

static const int VARIABLES = 3;
static const int BUCKETS = 64 * VARIABLES;
static const double CUTOFF = 0;
static const int LOGLEN = 10;
static const int MAXTIME = 13000;

static uint64_t iii = 27;
static uint64_t jjj = 17;
static uint64_t kkk = 37;

// 64-bit rotate left 
#define ROTL(d,lrot) ((d<<(lrot)) | (d>>(8*sizeof(d)-(lrot))))

class Random
{
public:
    Random(uint64_t seed)
    {
        m_a = m_b = 0xbadc0fee90dde55;
        m_a += seed;
    }
        
    virtual uint64_t Next() = 0;
    virtual void Fill(uint64_t* rsl) = 0;

    static const int c_arraysize = 256;
    uint64_t m_a, m_b, m_count;
};


class Bob7 : public Random
{
public:
    Bob7(uint64_t seed) : Random(seed)
    {
        for (int i = 0;  i < 10;  i++)
            (void)NextValue();
    }

    uint64_t PrevValue()
    {
        static const uint64_t m = 0x74ad5959e6a568d3;
        uint64_t x = m_a + m_count;
        m_a = m_b + x;
        m_b = m * x + ROTL(m_a, iii);
        m_count += 0x86d0890971771901;
        return m_b;
    }

    uint64_t NextValue()
    {
        static const uint64_t invM = 0x6538ccc9e172f5b;
        uint64_t x = invM * (m_b - ROTL(m_a, iii));
        m_b = m_a - x;
        m_a = x - m_count;
        m_count -= 0x86d0890971771901;
        return m_b;
    }
    
    uint64_t Next() { return NextValue(); }

    void Fill(uint64_t* rsl)
    {
        for (int i = 0;  i < c_arraysize;  i++)
        {
            rsl[i] = NextValue();
        }
    }

};



class Bob29 : public Random
{
public:
    Bob29(uint64_t seed) : Random(seed)
    {
        for (int i = 0;  i < 10;  i++)
            (void)NextValue();
    }

    uint64_t PrevValue()
    {
        static const uint64_t m = 0x74ad5959e6a568d3;
        uint64_t x = m_a + m_count;
        m_a = m_b + ROTL(x, iii);
        m_b = m * x + m_a;
        m_count += 0x86d0890971771901;
        return m_b;
    }

    uint64_t NextValue()
    {
        static const uint64_t invM = 0x6538ccc9e172f5b;
        uint64_t x = invM * (m_b - m_a);
        m_b = m_a - ROTL(x, iii);
        m_a = x - m_count;
        m_count -= 0x86d0890971771901;
        return m_b;
    }

    uint64_t Next() { return NextValue(); }

    void Fill(uint64_t* rsl)
    {
        for (int i = 0;  i < c_arraysize;  i++)
        {
            rsl[i] = NextValue();
        }
    }

};


// avalanche next and prev both 25, and time 5453: the winner
class Bob31 : public Random
{
public:
    Bob31(uint64_t seed) : Random(seed)
    {
        for (int i = 0;  i < 10;  i++)
            (void)NextValue();
    }

    uint64_t NextValue()
    {
        uint64_t m = 0x581af43eb71d8b3;
        uint64_t x = m_a + m_count++;
        m_a = m_b + ROTL(x, 12);
        m_b = m * x ^ ROTL(m_a, 28);
        return m_b;
    }

    uint64_t PrevValue()
    {
        uint64_t invM = 0x6cc3621b095c967b;
        uint64_t x = invM * (m_b ^ ROTL(m_a, 28));
        m_b = m_a - ROTL(x, 12);
        m_a = x - --m_count;
        return m_b;
    }
    uint64_t Next() { return NextValue(); }

    void Fill(uint64_t* rsl)
    {
        for (int i = 0;  i < c_arraysize;  i++)
        {
            rsl[i] = NextValue();
        }
    }

};


// avalanche next and prev both 25, but speed 6719.
class Bob103 : public Random
{
public:
    Bob103(uint64_t seed) : Random(seed)
    {
        for (int i = 0;  i < 10;  i++)
            (void)NextValue();
    }

    uint64_t NextValue()
    {
        static const uint64_t m = 0x74ad5959e6a568d3;
        uint64_t x = m_a + m_count;
        m_a = ROTL(m_b, 2) + x;
        m_b = m * x + ROTL(m_a, 18);
        m_count += 0x86d0890971771901;
        return m_b;
    }

    uint64_t PrevValue()
    {
        m_count -= 0x86d0890971771901;
        static const uint64_t invM = 0x6538ccc9e172f5b;
        uint64_t x = invM * (m_b - ROTL(m_a, 18));
        m_b = ROTL(m_a - x, (64-2));
        m_a = x - m_count;
        return m_b;
    }
    
    uint64_t Next() { return NextValue(); }

    void Fill(uint64_t* rsl)
    {
        for (int i = 0;  i < c_arraysize;  i++)
        {
            rsl[i] = NextValue();
        }
    }

};


// time 5969
class Bob125 : public Random
{
public:
    Bob125(uint64_t seed) : Random(seed)
    {
        for (int i = 0;  i < 10;  i++)
            (void)NextValue();
    }

    uint64_t PrevValue()
    {
        static const uint64_t m = 0x74ad5959e6a568d3;
        uint64_t x = m_a + m_count;
        m_a = ROTL(m_b, iii) + ROTL(x, jjj);
        m_b = m * x + m_a;
        m_count += 0x86d0890971771901;
        return m_b;
    }

    uint64_t NextValue()
    {
        static const uint64_t invM = 0x6538ccc9e172f5b;
        uint64_t x = invM * (m_b - m_a);
        m_b = ROTL(m_a - ROTL(x, jjj), (64-iii));
        m_a = x - m_count;
        m_count -= 0x86d0890971771901;
        return m_b;
    }
    
    uint64_t Next() { return NextValue(); }

    void Fill(uint64_t* rsl)
    {
        for (int i = 0;  i < c_arraysize;  i++)
        {
            rsl[i] = NextValue();
        }
    }

};


// time 6375
class Bob127 : public Random
{
public:
    Bob127(uint64_t seed) : Random(seed)
    {
        for (int i = 0;  i < 10;  i++)
            (void)NextValue();
    }

    uint64_t PrevValue()
    {
        static const uint64_t m = 0x74ad5959e6a568d3;
        uint64_t x = m_a + m_count;
        m_a = ROTL(m_b, iii) + ROTL(x, jjj);
        m_b = m * x + ROTL(m_a, iii);
        m_count += 0x86d0890971771901;
        return m_b;
    }

    uint64_t NextValue()
    {
        static const uint64_t invM = 0x6538ccc9e172f5b;
        uint64_t x = invM * (m_b - ROTL(m_a, iii));
        m_b = ROTL(m_a - ROTL(x, jjj), (64-iii));
        m_a = x - m_count;
        m_count -= 0x86d0890971771901;
        return m_b;
    }
    
    uint64_t Next() { return NextValue(); }

    void Fill(uint64_t* rsl)
    {
        for (int i = 0;  i < c_arraysize;  i++)
        {
            rsl[i] = NextValue();
        }
    }

};


// time 5922
class Bob293 : public Random
{
public:
    Bob293(uint64_t seed) : Random(seed)
    {
        for (int i = 0;  i < 10;  i++)
            (void)NextValue();
    }

    uint64_t PrevValue()
    {
        static const uint64_t m = 0x74ad5959e6a568d3;
        uint64_t x = ROTL(m_a, iii) + m_count;
        m_a = m_b + x;
        m_b = m * x + m_a;
        m_count += 0x86d0890971771901;
        return m_b;
    }

    uint64_t NextValue()
    {
        static const uint64_t invM = 0x6538ccc9e172f5b;
        uint64_t x = invM * (m_b - m_a);
        m_b = m_a  - x;
        m_a = ROTL(x - m_count, 64-iii);
        m_count -= 0x86d0890971771901;
        return m_b;
    }
    
    uint64_t Next() { return NextValue(); }

    void Fill(uint64_t* rsl)
    {
        for (int i = 0;  i < c_arraysize;  i++)
        {
            rsl[i] = NextValue();
        }
    }

};


// time 6531
class Bob317 : public Random
{
public:
    Bob317(uint64_t seed) : Random(seed)
    {
        for (int i = 0;  i < 10;  i++)
            (void)NextValue();
    }

    uint64_t PrevValue()
    {
        static const uint64_t m = 0x74ad5959e6a568d3;
        uint64_t x = ROTL(m_a, iii) + m_count;
        m_a = m_b + ROTL(x, jjj);
        m_b = m * x + m_a;
        m_count += 0x86d0890971771901;
        return m_b;
    }

    uint64_t NextValue()
    {
        static const uint64_t invM = 0x6538ccc9e172f5b;
        uint64_t x = invM * (m_b - m_a);
        m_b = m_a - ROTL(x, jjj);
        m_a = ROTL(x - m_count, 64-iii);
        m_count -= 0x86d0890971771901;
        return m_b;
    }
    
    uint64_t Next() { return NextValue(); }

    void Fill(uint64_t* rsl)
    {
        for (int i = 0;  i < c_arraysize;  i++)
        {
            rsl[i] = NextValue();
        }
    }

};


// time 6860
class Bob319 : public Random
{
public:
    Bob319(uint64_t seed) : Random(seed)
    {
        for (int i = 0;  i < 10;  i++)
            (void)NextValue();
    }

    uint64_t PrevValue()
    {
        static const uint64_t m = 0x74ad5959e6a568d3;
        uint64_t x = ROTL(m_a, iii) + m_count;
        m_a = m_b + ROTL(x, jjj);
        m_b = m * x + ROTL(m_a, kkk);
        m_count += 0x86d0890971771901;
        return m_b;
    }

    uint64_t NextValue()
    {
        static const uint64_t invM = 0x6538ccc9e172f5b;
        uint64_t x = invM * (m_b - ROTL(m_a, kkk));
        m_b = m_a - ROTL(x, jjj);
        m_a = ROTL(x - m_count, 64-iii);
        m_count -= 0x86d0890971771901;
        return m_b;
    }
    
    uint64_t Next() { return NextValue(); }

    void Fill(uint64_t* rsl)
    {
        for (int i = 0;  i < c_arraysize;  i++)
        {
            rsl[i] = NextValue();
        }
    }

};


// time 6500
class Bob389 : public Random
{
public:
    Bob389(uint64_t seed) : Random(seed)
    {
        for (int i = 0;  i < 10;  i++)
            (void)NextValue();
    }

    uint64_t PrevValue()
    {
        static const uint64_t m = 0x74ad5959e6a568d3;
        uint64_t x = ROTL(m_a, iii) + m_count;
        m_a = ROTL(m_b, jjj) + x;
        m_b = m * x + m_a;
        m_count += 0x86d0890971771901;
        return m_b;
    }

    uint64_t NextValue()
    {
        static const uint64_t invM = 0x6538ccc9e172f5b;
        uint64_t x = invM * (m_b - m_a);
        m_b = ROTL(m_a - x, 64-jjj);
        m_a = ROTL(x - m_count, 64-iii);
        m_count -= 0x86d0890971771901;
        return m_b;
    }
    
    uint64_t Next() { return NextValue(); }

    void Fill(uint64_t* rsl)
    {
        for (int i = 0;  i < c_arraysize;  i++)
        {
            rsl[i] = NextValue();
        }
    }

};


// time 6907
class Bob391 : public Random
{
public:
    Bob391(uint64_t seed) : Random(seed)
    {
        for (int i = 0;  i < 10;  i++)
            (void)NextValue();
    }

    uint64_t PrevValue()
    {
        static const uint64_t m = 0x74ad5959e6a568d3;
        uint64_t x = ROTL(m_a, iii) + m_count;
        m_a = ROTL(m_b, jjj) + x;
        m_b = m * x + ROTL(m_a, kkk);
        m_count += 0x86d0890971771901;
        return m_b;
    }

    uint64_t NextValue()
    {
        static const uint64_t invM = 0x6538ccc9e172f5b;
        uint64_t x = invM * (m_b - ROTL(m_a, kkk));
        m_b = ROTL(m_a - x, 64-jjj);
        m_a = ROTL(x - m_count, 64-iii);
        m_count -= 0x86d0890971771901;
        return m_b;
    }
    
    uint64_t Next() { return NextValue(); }

    void Fill(uint64_t* rsl)
    {
        for (int i = 0;  i < c_arraysize;  i++)
        {
            rsl[i] = NextValue();
        }
    }

};


// time 6922
class Bob413 : public Random
{
public:
    Bob413(uint64_t seed) : Random(seed)
    {
        for (int i = 0;  i < 10;  i++)
            (void)NextValue();
    }

    uint64_t PrevValue()
    {
        static const uint64_t m = 0x74ad5959e6a568d3;
        uint64_t x = ROTL(m_a, iii) + m_count;
        m_a = ROTL(m_b, jjj) + ROTL(x, kkk);
        m_b = m * x + m_a;
        m_count += 0x86d0890971771901;
        return m_b;
    }

    uint64_t NextValue()
    {
        static const uint64_t invM = 0x6538ccc9e172f5b;
        uint64_t x = invM * (m_b - m_a);
        m_b = ROTL(m_a - ROTL(x, kkk), 64-jjj);
        m_a = ROTL(x - m_count, 64-iii);
        m_count -= 0x86d0890971771901;
        return m_b;
    }
    
    uint64_t Next() { return NextValue(); }

    void Fill(uint64_t* rsl)
    {
        for (int i = 0;  i < c_arraysize;  i++)
        {
            rsl[i] = NextValue();
        }
    }

};



// count how many bits are set in a 64-bit integer, returns 0..64
static uint64_t count(uint64_t x)
{
  uint64_t c = x;

  c = (c & 0x5555555555555555) + ((c>>1 ) & 0x5555555555555555);
  c = (c & 0x3333333333333333) + ((c>>2 ) & 0x3333333333333333);
  c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4 ) & 0x0f0f0f0f0f0f0f0f);
  c = (c & 0x00ff00ff00ff00ff) + ((c>>8 ) & 0x00ff00ff00ff00ff);
  c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff);
  c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff);
  return c;
}


// initialize the data collection array 
static void datainit( uint64_t *data, uint64_t *data2)
{
    for (uint64_t i=0; i<BUCKETS; ++i)
    {
        data[i] = 0;   /* look for poor XOR mixing */
        data2[i] = 0;  /* look for poor additive mixing */
    }
}


// gather statistics on length overlapping subsequences of length 5 each
static void gather( Random* x, Random* y, uint64_t *data, uint64_t *data2, uint64_t length, int iter)
{
    for (uint64_t i=0; i<BUCKETS; ++i) {
        for (uint64_t k=0; k<length; ++k) {
            *y = *x;

            if (i<64)
                y->m_count ^= (1ULL<<i);
            else if (i<128)
                y->m_a ^= (1ULL<<(i-64));
            else if (i<192)
                y->m_b ^= (1ULL<<(i-128));
            else if (i<256)
                ; // y->m_c ^= (1ULL<<(i-192));
            else if (i<320)
                ; // y.m_d ^= (1ULL<<(i-256));
            else if (i<384)
                ; // y.m_count ^= (1ULL<<(i-256));

            uint64_t xv;
            uint64_t yv;
            for (uint64_t j=0; j<iter; ++j)
            {
                xv = x->Next();
                yv = y->Next();
            }

            // xor diff
            uint64_t q = count(xv ^ yv);
            data[i] += (q < 32 ? q : 64-q);

            // additive diff, plus graycode to reverse carry chains
            uint64_t h = xv - yv;
            h ^= (h>>1);
            q = count(h);
            data2[i] += (q < 32 ? q : 64-q);
        }
    }
}


double report( uint64_t *data, uint64_t *data2, uint64_t length)
{
    double worst = (uint64_t)-1;
    for (uint64_t i=0; i<BUCKETS; ++i)
    {
        if (worst > data[i])
        {
            worst = data[i];
        }
        if (worst > data2[i])
        {
            worst = data2[i];
        }
    }
    worst /= length;
    return worst;
}


double avalanche(Random* x, Random* y, int iter)
{
    uint64_t data[BUCKETS];
    uint64_t data2[BUCKETS];

    datainit(data, data2);
    gather(x, y, data, data2, (1<<6), iter);
    double worst = 0;
    for (uint64_t i=6; i<LOGLEN; ++i)
    {
        gather(x, y, data, data2, (1ULL<<i), iter);
        worst = report(data, data2, (1ULL<<(i+1)));
        if (worst < CUTOFF)
        {
            return worst;
        }
    }
    return worst;
}


uint64_t randtime(Random* x)
{
    static const uint64_t c_limit = 500000000ULL;
    uint64_t sum = 0;
    uint64_t aaa = GetTickCount();
    uint64_t cache[256];
    for (uint64_t i=0; i<c_limit; i+=256)
    {
        x->Fill(cache);
        for (int j=0; j<256; ++j)
            sum += cache[j];
    }
    uint64_t zzz = GetTickCount();

    if (sum == 1234) printf("the result matters!\n");
    return zzz-aaa;
}

void rngav(Random* x, Random* y, const char* name)
{
    double worst0 = avalanche(x, y, VARIABLES-1);
    if (worst0 < CUTOFF) return;
    double worst1 = avalanche(x, y, VARIABLES+0);
    if (worst1 < CUTOFF) return;
    double worst2 = avalanche(x, y, VARIABLES+1);
    if (worst2 < CUTOFF) return;
    double worst3 = avalanche(x, y, VARIABLES+2);
    if (worst3 < CUTOFF) return;
    double worst4 = avalanche(x, y, VARIABLES+3);
    if (worst4 < CUTOFF) return;
    uint64_t t = randtime(x);
    if (t > MAXTIME) return;
    printf("%s : avalanche = %f %f %f %f %f, time = %lu, %u, %u\n",
           name, worst0, worst1, worst2, worst3, worst4, t, iii, jjj);
}

int main(int argc, const char** argv)
{
    /*
    for (iii = 2;  iii < 64;  iii++)
    {
    {
        Bob7 x(0);
        Bob7 y(0);
        rngav(&x, &y, "Bob7");
    }
    {
        Bob29 x(0);
        Bob29 y(0);
        rngav(&x, &y, "Bob29");
    }
    {
        Bob31 x(0);
        Bob31 y(0);
        rngav(&x, &y, "Bob31");
    }
    {
        Bob103 x(0);
        Bob103 y(0);
        rngav(&x, &y, "Bob103");
    }
    {
        Bob125 x(0);
        Bob125 y(0);
        rngav(&x, &y, "Bob125");
    }
    {
        Bob127 x(0);
        Bob127 y(0);
        rngav(&x, &y, "Bob127");
    }
    {
        Bob293 x(0);
        Bob293 y(0);
        rngav(&x, &y, "Bob293");
    }
    {
        Bob317 x(0);
        Bob317 y(0);
        rngav(&x, &y, "Bob317");
    }
    {
        Bob319 x(0);
        Bob319 y(0);
        rngav(&x, &y, "Bob319");
    }
    {
        Bob389 x(0);
        Bob389 y(0);
        rngav(&x, &y, "Bob398");
    }
    {
        Bob391 x(0);
        Bob391 y(0);
        rngav(&x, &y, "Bob391");
    }
    {
        Bob413 x(0);
        Bob413 y(0);
        rngav(&x, &y, "Bob413");
    }
    }
    */
    for (iii=0; iii<64; iii++)
    {
        for (jjj=0; jjj<64; jjj++)
        {
            Bob31 x(0);
            Bob31 y(0);
            rngav(&x, &y, "Bob31");
        }
    }
    return 0;
}