/*********************************************************************
 *                                                                   *
 *    This program reads in the states of the Japanese ball          *
 *    puzzle from disk and does some analysis.                       *
 *                                                                   *
 *         Author = Mike Rosing                                      *
 *          Date  = Jan. 10, 2005                                    *
 *                                                                   *
 ********************************************************************/

#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>

#define SPACESIZE  (1024*1024*200)

unsigned int *StateSpace;

/*  I use 22 longs to represent all possible states.  The first 3 longs
    represent the balls with 3 bits for each ball.  The most signficant
    bit of the 0th long holds up/down toggle state - 0 is up, 1 is down.
    The last 9 bits of the 0th long hold row 0 if in up state and row 5
    if in down state.  The next 4 short words (2 longs) hold the rows 1
    through 4 using 15 bits, the msb is not used.  The next 19 longs hold
    3 byte pointers of which 23 bits are indexes to 22 long states, and 
    the most significant bit says if that state has been visited (set).
    19 longs = 4*19 = 76 bytes and I need 3*25 = 75 bytes.  Last byte
    is not used.
*/
/*  compare two states.  If same returns 1, 
    if different, returns 0.
*/

int compare( unsigned int *state1, unsigned int *state2)
{
    if( state1[0] != state2[0]) return 0;
    if( state1[1] != state2[1]) return 0;
    if( state1[2] != state2[2]) return 0;
    return 1;
}

/*  convert pointer to state block from an address to an integer */

unsigned long state2int( unsigned int *state)
{
    unsigned int k;

    k = (unsigned int) (state - StateSpace);
    k /= 22;
    k |= 0x800000;
    return k;
}

unsigned int *int2state( unsigned int k)
{
    unsigned int p;

    p = k & 0x7fffff;
    p *= 22;
    return (unsigned int*)(StateSpace +  p);
}

/*  store 24 bit pointer into correct offset location  */

void store24( unsigned int *state, int index, unsigned int value)
{
    char *ptr;

    ptr = (char *)state;
    ptr += 12 + 3*index;
    *ptr++ = (value >> 16) & 0xff;
    *ptr++ = (value >> 8) & 0xff;
    *ptr = value & 0xff;
}

/*  get 24 bit value out of location stored in state structure  */

unsigned int get24( unsigned int *state, int index)
{
    char *ptr;
    unsigned int x;

    ptr = (char *)state;
    ptr += 12 + 3*index;
    x = ((*ptr++) << 16) & 0xff0000;
    x |= ((*ptr++) << 8) & 0xff00;
    x |= (*ptr) & 0xff;
    return x;
}

/*  convert state date back into matrix for checking.
    not to be used in full run!!  */

void unpack( unsigned int *state, int matrix[6][5])
{
    int row, col;
    unsigned int mask;

    mask = state[0];
    for( col=0; col<5; col++)
    {
	matrix[0][col] = -1;
	matrix[5][col] = -1;
    }
    if( state[0] & 0x80000000)
    {
	matrix[5][0] = (mask & 0x1c0) >> 6;
	matrix[5][2] = (mask & 0x38) >> 3;
	matrix[5][4] = mask & 7;
    }
    else
    {
	matrix[0][0] = (mask & 0x1c0) >> 6;
	matrix[0][2] = (mask & 0x38) >> 3;
	matrix[0][4] = mask & 7;
    }
    mask = 0x70000000;
    for(col=0; col<5; col++)
    {
	matrix[1][col] = (state[1] & mask) >> (28 - col*3);
	mask >>= 3;
    }
    mask >>= 1;
    for(col=0; col<5; col++)
    {
	matrix[2][col] = (state[1] & mask) >> (12 - col*3);
	mask >>= 3;
    }
    mask = 0x70000000;
    for(col=0; col<5; col++)
    {
	matrix[3][col] = (state[2] & mask) >> (28 - col*3);
	mask >>= 3;
    }
    mask >>= 1;
    for(col=0; col<5; col++)
    {
	matrix[4][col] = (state[2] & mask) >> (12 - col*3);
	mask >>= 3;
    }
}

main()
{
    unsigned int *genstate, *available, *oldstate, *endstate;
    unsigned int *stateptr, *endptr;
    int matrix[6][5];
    int row, col, state, i, k;
    unsigned int pckd;
    char inchr[2], filename[64];
    int statefile;

    StateSpace = malloc(sizeof(int)*SPACESIZE);
    if (StateSpace == NULL) 
    {
	printf("sorry, can't get that much space\n");
	exit(0);
    }
    stateptr = malloc( sizeof(int)*16*1024*1024);
    if( stateptr == NULL)
    {
      printf("can't allocate state pointer ram\n");
      exit(0);
    }
    endptr = malloc( sizeof(int)*16*1024*1024);
    if( endptr == NULL)
    {
      printf("can't allocate end pointer ram\n");
      exit(0);
    }


/*  recover previously computed data from disk  */

    printf("Read data from what file: ");
    scanf("%s", filename);
    statefile = open(filename, O_RDWR );
    if(statefile < 0) 
    {
      printf("failed to open file %s\n", filename);
      exit(0);
    }
    available = (unsigned int*)StateSpace;
    state = read( statefile, available, 16);
    while( (state>0) && (available < (unsigned int*)(StateSpace + SPACESIZE)))
    {
      available += 4;
      state = read( statefile, available, 16);
    }
    if(state<0) perror("what the fuck:");
    close(statefile);
    if( available < StateSpace + SPACESIZE)
      printf("Number of states read = %d\n", (available - StateSpace)/4);
    else
      printf("FILE TOO BIG TO HOLD IN RAM\n");
    endstate = available;
//    printf("last address is %x\n", endstate);

/*  build table of pointers into state lists, both start and end  */

    oldstate = StateSpace;
    state = 0;
    while (oldstate < endstate)
    {
      stateptr[state] = ((unsigned int) (oldstate - StateSpace))/4;
      while((oldstate[3] != 0xffffffff) && (oldstate < endstate)) oldstate += 4;
      endptr[state] = ((unsigned int) (oldstate - StateSpace))/4;
      state++;
      if(state>16*1024*1024) break;
      oldstate += 4;
    }
    if(state < 16*1024*1024)
      printf("number of paths is %d\n", state);
    else
      printf("TOO MANY STATES TO DEAL WITH!!!\n");

/*    available = (unsigned long *)(endptr[state-1]*4 + StateSpace);
    if( available < (endstate - 4)) 
      printf("Not hitting the end??? %x  %x\n", available, endstate-4);

/*  and remove any duplicates  */

    for( i=0; i<state; i++)
    {
      if(stateptr[i] > 16*1024*1024) continue;
      available = (unsigned int *)(endptr[i]*4 + StateSpace);
      genstate = (unsigned int *) (stateptr[i]*4 + StateSpace);
//      if( compare( available, genstate) || (endptr[i] == stateptr[i]))
      if( compare( available, genstate))
      {
	stateptr[i] = 16*2048*1024;
	continue;
      }
      for( k=i+1; k<state; k++)
      {
	oldstate = (unsigned int *) (stateptr[k]*4 + StateSpace);
	if( compare( genstate, oldstate)) stateptr[k] = 16*2048*1024;
      }
    }

/*  save pointers to non duplicate states into another file  */

    printf("Save pointers to what file: ");
    scanf("%s", filename);
    statefile = open(filename, O_RDWR | O_CREAT, S_IRUSR | S_IWUSR | 
		     S_IRGRP |S_IWGRP | S_IROTH );
    if(statefile < 0) 
    {
      printf("failed to create file %s\n", filename);
      exit(0);
    }
    k =0;
    for(i=0; i<state; i++)
    {
      if( stateptr[i] > 16*1024*1024) continue;
      write( statefile, &stateptr[i], 4);
      k++;
    }
    close( statefile);
    printf("There are %d non duplicated states\n", k);

}