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

static uint64_t s_gen = 0;
//
// Dice allows a user program to call dice->choose(n) to make choices, but the user program will be called
// for all legal combinations of choices.  It's a poor man's prolog.
// The user needs to avoid calling choose(0).
//
class Dice
{
    static const uint64_t sc_uint64_tbits = 64; // bits per uint64_t
    static const uint64_t sc_size = 1024; // number of uint64_t's in state
    static const uint64_t sc_bits = sc_uint64_tbits * sc_size; // total number of bits
    
    uint64_t m_state[sc_size]; // the actual dice bits
    uint64_t m_offset; // the lowest used dice bit

    
    Init()
    {
        // initialize the state to zero
        for (uint64_t i=0; i<sc_size; ++i)
        {
            m_state[i] = 0;
        }
    }
    

    // Set bits sc_bits-offset-logn to sc_bits-offset-1
    void Mask(uint64_t logn)
    {
        uint64_t index = m_offset / sc_uint64_tbits;
        uint64_t shift = m_offset % sc_uint64_tbits;
        uint64_t mask = (((uint64_t)1)<<logn)-1;
        m_state[index] |= (mask << shift);
        if (sc_uint64_tbits-shift < logn)
        {
            m_state[index+1] |= (mask >> (sc_uint64_tbits-shift));
        }
    }
    
    
    // read bits sc_bits-offset-logn to sc_bits-offset-1
    uint64_t Read(uint64_t logn)
    {
        uint64_t index = m_offset / sc_uint64_tbits;
        uint64_t shift = m_offset % sc_uint64_tbits;
        uint64_t mask = (((uint64_t)1)<<logn)-1;
        uint64_t result = (m_state[index] & (mask << shift)) >> shift;
        if (sc_uint64_tbits-shift < logn)
        {
            result |= (m_state[index+1] & (mask >> (sc_uint64_tbits-shift))) << (sc_uint64_tbits-shift);
        }
        return result;
    }
    
    
    // Increment the state at sc_bits-offset-1.  Return TRUE if we can't.
    bool Inc()
    {
        uint64_t index = m_offset / sc_uint64_tbits;
        uint64_t shift = m_offset % sc_uint64_tbits;
        m_state[index] += (((uint64_t)1)<<shift);
        while (m_state[index] == 0 && ++index < sc_size)
        {
            m_state[index] += 1;
        }
        return (index == sc_size);
    }
    
    
public:

    // choose a value in 0..n-1
    uint64_t Choose(uint64_t n)
    {
        uint64_t logn;
        uint64_t result;
        
        // check that the dice aren't too big
        if (n > 0x8000000000000000L) {
            fprintf(stderr, "Error: Can't do choose(%ull), %ull is too big\n", n, n);
            exit(1);
        }
        
        // figure out how many bits to use
        for (logn=0; (((uint64_t)1)<<logn) < n; ++logn) ;

        if (m_offset < logn)
        {
            fprintf(stderr, "Error: Too many dice rolls\n");
            exit(1);
        }
        
        // use this many bits
        m_offset -= logn;

        // read the result
        result = Read(logn);
        
        if (result >= n-1) 
        {
            // If we've reached n-1, pretend we've reached (1<<logn)-1
            if (result == n-1)
            {
                Mask(logn);
            }
            else
            {
                result = n-1;
            }
        }
        
        return result;
    }

    
    void Exec(void (*callback)(Dice *d, void *context), void *context)
    {
        // call user callback with all possible sets of choices
        for (;;)
        {
            // call the user's callback with a new set of choices
            m_offset = sc_bits;
            (*callback)(this, context);
            
            // increment the state; quit when we wrap around
            if (Inc())
            {
                break;
            }
        }
    }

    
    Dice()
    {
        Init();
    }

    
    ~Dice()
    {
    }
};

class Generator
{
public:
    static void PlaceCount(Dice* d, bool reverse)
    {
        printf(" %s m_count++", reverse ? "-" : "+");
    }

    static void Decorate(const char* name, int choice)
    {
        switch(choice)
        {
        case 0:
            printf("%s", name);
            break;
        case 1:
            printf("m * %s", name);
            break;
        case 2:
            printf("ROTL(%s, 27)", name);
            break;
        }
        // printf("%s", name);
    }

    static void Line(Dice* d, const char* lhs, const char* rhs, const char* optA, const char* optB, bool count, bool o1, bool o2)
    {
        printf("%s = ", lhs);
        Decorate(rhs, d->Choose(3));
        if (o1)
        {
            printf(" %s ", "+");
            Decorate(optA, d->Choose(3));
        }
        if (o2)
        {
            printf(" %s ", "+");
            Decorate(optB, d->Choose(3));
        }
        if (count) PlaceCount(d, false);
        printf(";\n");
    }


    static void PLine(Dice* d, const char* lhs, const char* rhs, const char* optA, const char* optB, bool count, bool o1, bool o2)
    {
        printf("%s = ", lhs);
        Decorate(rhs, 0);
        if (o1)
        {
            printf(" %s ", "-");
            Decorate(optA, 0);
        }
        if (o2)
        {
            printf(" %s ", "-");
            Decorate(optB, 0);
        }
        if (count) PlaceCount(d, true);
        printf("\n");
    }
    
    static void Test(Dice* d, void* ctx)
    {
        int good = *(int *)ctx;
        s_gen++;
        int countpos = (good>>10) & 3;
        int retval = (good>>8) & 3;
        int a1 = !!(good & 128);
        int a2 = !!(good & 64);
        int b1 = !!(good & 32);
        int b2 = !!(good & 16);
        int c1 = !!(good & 8);
        int c2 = !!(good & 4);
        int d1 = !!(good & 2);
        int d2 = !!(good & 1);
        int countopt = a1+a2+b1+b2+c1+c2+d1+d2;
        if (countopt != 1)
            return;
        printf("\n\n\n");
        printf("// group: %d\n", good);
        printf("class Bob%d : public Random\n", s_gen);
        printf("{\n");
        printf("public:\n");
        printf("    Bob%d(uint64_t seed) : Random(seed)\n", s_gen);
        printf("    {\n");
        printf("        for (int i = 0;  i < 10;  i++)\n");
        printf("            (void)Next();\n");
        printf("    }\n");
        printf("\n");
        printf("    uint64_t Next()\n");
        printf("    {\n");
        printf("        static const uint64_t m = 0x74ad5959e6a568d3;\n");
        Line(d,"        uint64_t x", "m_a", "m_b", "m_c", (countpos == 0), a1, a2);
        Line(d,"        m_a", "m_b", "m_c", "x", (countpos == 1), b1, b2);
        Line(d,"        m_b", "m_c", "x", "m_a", (countpos == 2), c1, c2);
        Line(d,"        m_c", "x", "m_a", "m_b", (countpos == 3), d1, d2);
        printf("        return %s;\n", retval == 0 ? "m_a" : retval == 1 ? "m_b" : retval == 2 ? "m_c" : "x");
        printf("    }\n");
        printf("\n");
        printf("    uint64_t Prev()\n");
        printf("    {\n");
        printf("        static const uint64_t m = 0x74ad5959e6a568d3;\n");
        PLine(d,"        uint64_t x", "m_c", "m_a", "m_b", (countpos == 3), d1, d2);
        PLine(d,"        m_c", "m_b", "x", "m_a", (countpos == 2), c1, c2);
        PLine(d,"        m_b", "m_a", "m_c", "x", (countpos == 1), b1, b2);
        PLine(d,"        m_a", "x", "m_b", "m_c", (countpos == 0), a1, a2);
        printf("        return %s;\n", retval == 0 ? "m_a" : retval == 1 ? "m_b" : retval == 2 ? "m_c" : "x");
        printf("    }\n");
        printf("\n");
        printf("    void Fill(uint64_t* rsl)\n");        
        printf("    {\n");
        printf("        for (int i = 0;  i < c_arraysize;  i++)\n");
        printf("        {\n");
        printf("            rsl[i] = Next();\n");
        printf("        }\n");
        printf("    }\n");
        printf("\n");
        printf("};\n");
    }
};

static int t_good[] =
{
4,6,7,8,10,12,13,15,
19,20,22,34,37,41,77,97,
130,133,135,161,162,163,193,197,
199,267,268,269,274,275,276,277,
278,280,281,282,283,293,297,325,
329,453,518,519,522,525,530,531,
534,537,538,539,541,546,581,585,
609,642,645,673,705,781,783,787,
790,794,795,797,799,803,805,898,
899,900,902,930,965,1028,1030,1034,
1042,1043,1044,1049,1058,1065,1091,1093,
1094,1097,1121,1156,1157,1158,1160,1185,
1219,1284,1287,1291,1293,1298,1300,1314,
1347,1349,1353,1425,1426,1474,1540,1542,
1546,1547,1549,1554,1555,1556,1570,1603,
1605,1609,1668,1670,1697,1713,1729,1730,
1731,1732,1733,1805,1807,1810,1811,1812,
1817,1858,1859,1861,1862,1865,1922,1923,
1924,1926,1928,1938,1969,2052,2055,2063,
2066,2067,2117,2149,2180,2193,2209,2308,
2315,2319,2322,2323,2325,2341,2371,2373,
2377,2389,2393,2409,2436,2449,2481,2497,
2571,2575,2579,2581,2585,2597,2605,2627,
2629,2633,2645,2649,2657,2665,2705,2721,
2753,2831,2834,2835,2841,2853,2865,2883,
2885,2889,2901,2905,2909,2929,2946,2947,
3076,3078,3085,3087,3090,3091,3094,3095,
3099,3109,3113,3121,3141,3202,3209,3332,
3340,3341,3346,3354,3357,3362,3365,3369,
3373,3425,3458,3463,3474,3521,3524,3525,
3588,3590,3591,3594,3595,3596,3599,3602,
3603,3606,3607,3610,3611,3612,3629,3714,
3717,3719,3721,3723,3729,3730,3731,3777,
3781,3877,3885,3889,3890,3911,3970,3971,
3975,3977,3978,3979,3980,3986,3987,4039
};

int main(int argc, const char**argv)
{
    for (int i=0; i<sizeof(t_good)/sizeof(int); i++)
    {
        Dice d;
        d.Exec(&Generator::Test, &t_good[i]);
    }

    /*
    for (int i=1; i<=s_gen;  i++)
    {
        printf("    {\n");
        printf("        Bob%d x(0);\n", i);
        printf("        uint64_t sum = 0;\n");
        printf("        uint64_t a = GetTickCount();\n");
        printf("        for (uint64_t i=0; i<c_limit; i++)\n");
        printf("            sum += x.Next();\n");
        printf("        uint64_t z = GetTickCount();\n");
        printf("        printf(\"time Bob%d: %%lu, sum=%%lx\\n\", z-a, sum);\n", i);
        printf("    }\n");
    }
    */
    return 0;
}