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

/*
 * This program creates a graph with all the possible configuration of an
 * 1-dimensional r=2 CA that can be read by http://www.graphviz.org/.
 * You can use graphviz to create the images.
 * 
 * Usage example:
 * ./cagraph 1718195561 5
 * dot -Tpng graph-rule1718195561-n5.dot > graph-rule1718195561-n5.png
 *
 * You can get some CA rules here:
 * http://arhuaco.blogspot.com/2005/07/prng-with-one-dimensional-r1-cellular.html
 *
 */


#define PROGRAM_NAME "cagraph"
#define DEBUG 1

#define   MALLOC(var,size)      \
            (var) = malloc(size);    \
       	    if(!(var))               \
	            fprintf(stderr, "%s:%d: out of memory\n", __FILE__, __LINE__), \
	            exit(EXIT_FAILURE); \

#define   ASSERT(x) \
            if(!(x)) \
              fprintf(stderr, "%s:%d: ASSERT failed\n", __FILE__, __LINE__), \
	          exit(EXIT_FAILURE);

typedef struct CA CA;

/* Iterate the CA */
void          ca_iterate          (CA *ca, unsigned int steps);

/* Create the cellular automaton */
CA *          ca_create           (unsigned int width, unsigned int rule);

/* Set the rule for the transition table */
void          ca_rule_set         (CA *ca, unsigned int rule);

/* Free the memory held by the cellular automaton */
void          ca_destroy          (CA *ca);

/* Print the cellular automaton */
void          ca_print            (CA *ca);

/* Copy the initial configuration from an integer */
void          ca_int_init         (CA *ca, int conf);

/* Get the integer of a CA configuration */
unsigned int  ca_int_get          (CA *ca);

int
main(int argc, char *argv[])
{
  int i;

  int N;
  int NSTATES;

  unsigned int rule;
  CA *ca;

  FILE *p;
  char filename[256];

  if (argc != 3)
  {
    fprintf(stderr, "usage: %s rule ca-size\n", PROGRAM_NAME);
    exit(EXIT_FAILURE);
  }

  sscanf(argv[1], "%u", &rule);

  sscanf(argv[2], "%d", &N);

  if (DEBUG)
    fprintf(stderr, "rule %u\nN=%d\n", rule, N);
  
  ca = ca_create(N, rule);

  sprintf(filename, "graph-rule%u-n%d.dot", rule, N);
  filename[255] = 0;

  p = fopen(filename, "w");

  if (!p)
  {
    fprintf(stderr, "couldn't open file '%s'\n", filename);
    exit(EXIT_FAILURE);
  }
  
  fprintf(p, "digraph Graph_rule%u_n%d{\n", rule, N);

  NSTATES =  (2 << (N - 1));
  
  for (i = 0; i < NSTATES; ++i)
  {
    int dest;
    
    ca_int_init(ca, i); 
    ca_iterate(ca, 1);
    dest = ca_int_get(ca);
            
    fprintf(p, " %d -> %d;\n", i, dest);
  }

  fprintf(p, "}\n");
	
  fclose(p);
          
  ca_destroy(ca);

  return EXIT_SUCCESS;
}

struct CA
{
  unsigned int width;
  unsigned int rule;
  char *cell;
};

CA *
ca_create(unsigned int width, unsigned int rule)
{
  CA *new;

  MALLOC(new, sizeof(CA));
  
  new->rule  = rule;
  new->width = width;
  
  MALLOC(new->cell, width + 2); 

  return new;
}

void
ca_rule_set(CA *ca, unsigned int rule)
{
  ASSERT(ca);
  ASSERT(ca->cell);
  ca->rule = rule;
}
      
void
ca_destroy(CA *ca)
{
  ASSERT(ca);
  ASSERT(ca->cell);
  
  free(ca->cell);
  free(ca);
}

void
ca_print(CA *ca)
{
  unsigned int i;
  
  for (i = 0; i < ca->width; i++)
  {
      printf("%c", '0' + ca->cell[i]);
  }
}

void     ca_int_init            (CA *ca, int conf)
{
  int i;
 
  /* We need to itereate when conf == 0, too */
  for (i = ca->width - 1; i >= 0; i--)
  {
    ca->cell[i] = conf % 2;
    conf /= 2;
  }
}

unsigned int  ca_int_get          (CA *ca)
{
  int i;
  int sum = 0;
  int mul = 1;
 
  for (i = ca->width - 1; i >= 0; i--)
  {
    if (ca->cell[i])
      sum += mul;

    mul *= 2;
  }

  return sum;
}
	
/*
 * Now we iterate the CA inplace.
 * I sould've done this a long time ago.
 *
 * The ca array _must_ have two extra locations.
 */

void ca_iterate (CA *ca, unsigned int steps)
{
  unsigned int i, col, lookup;

  ASSERT(ca);
  ASSERT(steps);
  ASSERT(ca->cell);
  ASSERT(ca->width > 2);

  for (i = 0; i < steps; i++)
  {
     ca->cell[ca->width]     = ca->cell[0];
     ca->cell[ca->width + 1] = ca->cell[1];
     
     lookup = ca->cell[ca->width - 2] << 3 |
              ca->cell[ca->width - 1] << 2 |
              ca->cell[0] << 1 |
              ca->cell[1];

     for (col = 0; col < ca->width; col++)
     {
        lookup = (lookup << 1 | ca->cell[col + 2]) & 0x001F;

        ASSERT(lookup >=0 && lookup <= 31);
        
        ca->cell[col] = (ca->rule & (1 << lookup)) >> lookup;
     }
  }
}