/*
-----------------------------------------------------------------------
Dice is essentially prolog in C.

The main program (the test harness) calls a user routine, driver(), 
which has to be finite and deterministic, except that it can call a 
routine choose(n) that returns a choice in 0..n-1.  choose(n) is like 
a throw of dice.  But the test harness calls driver() multiple times,
once for all possible settings of all its calls to choose(n).  So 
driver() gets to explore all its possible parallel universes.  The
user should also implement init(), which initializes some reusable
context for driver().
-----------------------------------------------------------------------
*/

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

typedef unsigned int u4;        /* unsigned 4-byte value */
#define U4BITS 32               /* bits per u4 */

static u4 choose(u4 n);         /* choose is defined by the test harness */
static void *init();            /* the user code has to define init() */
static void driver(void *ctx);  /* the user code has to define driver() */

/*
-----------------------------------------------------------------------
User code goes here: it has to define init() and driver()
-----------------------------------------------------------------------
*/

void* init()
{
    return (void*)0;
}

void driver(void *ctx)
{
    for (int i=0; i<10; i++)
    {
        int x = choose(6) + 1;
        printf("%d ", x);
        if (x != 3)
        {
            printf("\n");
            return;
        }
    }
    printf("\n");
    printf("Yes, it is possible to roll 3 ten times in a row!\n");
}

/*
-----------------------------------------------------------------------
The test harness is below
-----------------------------------------------------------------------
*/

#define DICE_SIZE 256  /* max bits of entropy from the dice */

static u4 dice_state[DICE_SIZE/U4BITS];  /* the actual dice bits */
static u4 dice_offset;  /* the lowest used dice bit */



/* Set bits DICE_SIZE-offset-logn to DICE_SIZE-offset-1 */
void dice_mask(u4 *state, u4 offset, u4 logn)
{
    offset -= logn;
    u4 index = offset / U4BITS;
    u4 shift = offset % U4BITS;
    u4 mask = (1<<logn)-1;
    state[index] |= (mask << shift);
    if (U4BITS-shift < logn)
    {
        state[index+1] |= (mask >> (U4BITS-shift));
    }
}



/* read bits DICE_SIZE-offset-logn to DICE_SIZE-offset-1 */
u4 dice_read(u4 *state, u4 offset, u4 logn)
{
  offset -= logn;
  u4 index = offset / U4BITS;
  u4 shift = offset % U4BITS;
  u4 mask = (1<<logn)-1;
  u4 result = (state[index] & (mask << shift)) >> shift;
  if (U4BITS-shift < logn)
  {
      result |= (state[index+1] & (mask >> (U4BITS-shift))) << (U4BITS-shift);
  }
  return result;
}



/* Increment the state at DICE_SIZE-offset-1.  Return TRUE if we can't. */
int dice_inc(u4 *state, u4 offset)
{
  u4 index = offset / U4BITS;
  u4 shift = offset % U4BITS;
  state[index] += (1<<shift);
  while (state[index] == 0 && ((++index) < (DICE_SIZE/U4BITS)))
  {
      state[index] += 1;
  }
  return (index == DICE_SIZE/U4BITS);
}



/* choose a value in 0..n-1 */
static u4 choose(u4 n)
{
    int logn;
    int result;

    if (sizeof(u4) != 4)
    {
        fprintf(stderr, "Error: u4 should be a 4-byte type, not %d", sizeof(u4));
        exit(1);
    }
    
    /* check that the dice aren't too big */
    if (n > 0x80000000)
    {
        fprintf(stderr, "Error: Can't do choose(%ul), %ul is too big\n", n, n);
        exit(1);
    }
    
    /* figure out how many bits to use */
    for (logn=0; (1<<logn) < n; ++logn)
        ;
    if (dice_offset < logn)
    {
        fprintf(stderr, "Error: Too many dice rolls\n");
        exit(1);
    }
    
    /* read the result */
    result = dice_read(dice_state, dice_offset, logn);
    
    if (result >= n-1)
    {
        /* If we've reached n-1, pretend we've reached (1<<logn)-1 */
        if (result == n-1)
        {
            dice_mask(dice_state, dice_offset, logn);
        }
        else
        {
          result = n-1;
        }
    }

    /* record how many bits we used and report the result */
    dice_offset -= logn;
    
    return result;
}


/* call driver() with all possible values of all calls to choose() */
int main()
{
    u4 i;
    void *ctx = init();
    
    /* initialize the state to zero */
    for (i=0; i<DICE_SIZE/U4BITS; ++i)
    {
        dice_state[i] = 0;
    }
    
    /* call driver, then increment the state */
    for (;;)
    {
        /* call the user's driver with a new state */
        dice_offset = DICE_SIZE;
        driver(ctx);
        
        /* increment the state; quit when we wrap around */
        if (dice_inc(dice_state, dice_offset))
            break;
    }

    return 0;
}