/***

    gcc -O2 direct5_fourmis.c

    On my 1733 MHz Pentium M laptop, this runs at ~ 250'000'000 ant
    steps per second.

Langton's Ant 100 or RLL (right-left-left).  See introduction e.g. at
http://www.fortunecity.com/emachines/e11/86/langton.html .

You can cleanly interrupt the running program with a Ctrl-C or a SIGTERM
signal and restart it later; it will save its state and resume from
there.  The SIGHUP signal forces a state dump but the program continues
afterwards.  The SIGUSR1 signal only forces the thumb file to be
written.

The checkerboard is represented as follows in memory:

                      | ...         |
                      +-------------+
           ...        | address P-1 | ...
    --+---------------+-------------+---------------+--
  ... | addr P-HEIGHT | address P   | addr P+HEIGHT | ...
    --+---------------+-------------+---------------+--
           ...        | address P+1 | ...
                      ...

Each box is one byte, which packs 5 adjacent pixels, each of which
can be in three possible states:

                      +-------------+
                      | 81 27 9 3 1 |
                      +-------------+

At a larger scale, the infinite plane is divided into square "zones" of
about 4 MB each.  The RAM and the dump file contain complete zones.  As
the program runs, new zones are allocated on demand.  In each zone, the
two border rows and the two border columns are filled with the
otherwise-invalid byte value 243, playing the role of sentinel.

 ***/

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <stdarg.h>
#include <string.h>
#include <time.h>
#include <signal.h>


#define MAGIC         0x63463544     /* D5Fc */
#define DUMP_FILE     "zones.dump"
#define LOG_FILE      "zones.log"
#define PID_FILE      "zones.pid"
#define ZONE_HEIGHT   4567     /* prime number */
//#define ZONE_HEIGHT   127     /* prime number */
#define ZONE_WIDTH    ((ZONE_HEIGHT+2)/5)
#define ZONE_BYTES    (ZONE_WIDTH * ZONE_HEIGHT)   /* almost 4MB */
#define ZONE_SIZE     ((ZONE_BYTES + 31) & ~ 31)   /* aligned up */

#define THUMB_FILE    "zones.ppm"
#define THUMB_WIDTH   12
#define THUMB_HEIGHT  THUMB_WIDTH

/* configuration for automatic saving and stopping */
#define STOP_AT_N_ZONES        2400
#define SAVE_EVERY_N_SECONDS   34567

typedef int int32;
typedef unsigned int uint32;


typedef struct {
  uint32 magic;
  uint32 zone_width, zone_height, zone_size;
  int32 numzones;
  int32 curzx, curzy, curp, curdir;
  int32 pad[7];
} header_t;

typedef struct {
  int32 zx, zy;
  uint32 creation_time;
  int32 pad[5];
  unsigned char data[ZONE_SIZE];
} zonedata_t;

struct zone_s {
  struct zone_s *above, *below, *left, *right;
  struct zone_s *next;  /* linked list in a random order */
  void *pad[3];
  zonedata_t z;
};

struct zone_s *zones = NULL;
header_t header;
time_t lastsync;
volatile long stopflag;   /* 12*512: normal operation
                                 -1: shutdown requested
                                 -2: save() requested
                                 -3: save_thumb() requested */

void Log(char *msg,...)
{
  va_list ap;
  time_t now;
  FILE *logfile;

  va_start(ap, msg);
  vprintf(msg, ap);
  printf("\n");
  va_end(ap);

  logfile = fopen(LOG_FILE, "a");
  if (logfile == NULL)
    {
      fprintf(stderr, "warning: cannot open log file\n");
    }
  else
    {
      now = time(NULL);
      va_start(ap, msg);
      vfprintf(logfile, msg, ap);
      fprintf(logfile, "\t\t%.2f\t%s",
              ((double) clock()) / CLOCKS_PER_SEC,
              asctime(gmtime(&now)));
      va_end(ap);
      fclose(logfile);
    }
}

void Error(char *msg)
{
  Log("ERROR: %s", msg);
  exit(1);
}

void PError(char *msg)
{
  perror("langton-ant");
  Error(msg);
}

void check_assertions(void)
{
  printf("source code:    %s\n", __FILE__);
  printf("zone width:     %d pixels (%d columns)\n", ZONE_WIDTH*5, ZONE_WIDTH);
  printf("zone height:    %d pixels\n", ZONE_HEIGHT);
  printf("zone size:      %d kb\n", ZONE_SIZE / 1024);
}

void readall(FILE *f, void *data, size_t size)
{
  int read = fread(data, size, 1, f);
  if (read != 1)
    Error("fread(): not enough data");
}

void writeall(FILE *f, const void *data, size_t size)
{
  int written = fwrite(data, size, 1, f);
  if (written != 1)
    Error("fwrite() failed");
}

/************************************************************/

void save_thumb(const char *filename)
{
  int zxmin=0, zxmax=0, zymin=0, zymax=0;
  struct zone_s *zp;
  int ppmw, ppmh;
  unsigned char *ppmdata;
  FILE *f;
  char tmpname[256];
  
  for (zp = zones; zp; zp = zp->next)
    {
      int zx = zp->z.zx;
      int zy = zp->z.zy;
      if (zx < zxmin) zxmin = zx;
      if (zx > zxmax) zxmax = zx;
      if (zy < zymin) zymin = zy;
      if (zy > zymax) zymax = zy;
    }

  ppmw = (zxmax-zxmin+2) * THUMB_WIDTH;
  ppmh = (zymax-zymin+2) * THUMB_HEIGHT;
  ppmdata = malloc(ppmw*ppmh);
  if (ppmdata == NULL)
    Error("out of memory in save_thumb()");
  memset(ppmdata, 255, ppmw*ppmh);

  for (zp = zones; zp; zp = zp->next)
    {
      int x0 = (zp->z.zx - zxmin) * THUMB_WIDTH;
      int y0 = (zp->z.zy - zymin) * THUMB_HEIGHT;
      unsigned char *dest = ppmdata + x0 + y0*ppmw + \
          (THUMB_WIDTH/2) + (THUMB_HEIGHT/2)*ppmw;
      unsigned char *src = zp->z.data;
      int i, j;
      int bkgnd = (zp->z.zx ^ zp->z.zy) & 1 ? 0xF0 : 0xE0;
      for (j=0; j<THUMB_HEIGHT; j++)
        for (i=0; i<THUMB_WIDTH; i++)
          {
            int sample_x = 1 + i*(ZONE_WIDTH-2) / THUMB_WIDTH;
            int sample_y = 1 + j*(ZONE_HEIGHT-2) / THUMB_HEIGHT;
            int c = src[sample_y + sample_x*ZONE_HEIGHT];
            dest[i + j*ppmw] = bkgnd ^ c;
          }
    }

  strcpy(tmpname, filename);
  strcat(tmpname, "~");
  f = fopen(tmpname, "wb");
  if (f == NULL)
    Error("cannot create thumb file");
  fprintf(f, "P5\n");
  fprintf(f, "%d %d\n", ppmw, ppmh);
  fprintf(f, "255\n");
  writeall(f, ppmdata, ppmw*ppmh);
  if (fclose(f) != 0)
    Error("fclose() failed");
  free(ppmdata);
  if (rename(tmpname, filename) != 0)
    PError("rename() failed");
}

/************************************************************/

void save(const char *filename)
{
  FILE *f;
  char tmpname[256];
  struct zone_s* zp;
  int i;

  strcpy(tmpname, filename);
  strcat(tmpname, "~");
  Log("*** SAVING ***    ");
  f = fopen(tmpname, "wb");
  if (f == NULL)
    Error("fopen() failed in save()");

  if (header.magic != MAGIC)
    Error("bogus header in memory??");
  writeall(f, &header, sizeof(header));

  for (zp = zones; zp; zp = zp->next)
    writeall(f, &zp->z, sizeof(zonedata_t));

  if (fclose(f) != 0)
    Error("fclose() failed");

  if (rename(tmpname, filename) != 0)
    PError("rename() failed");
  Log("wrote %s", filename);
  lastsync = time(NULL);
}

void load(const char *filename)
{
  FILE *f;
  int i;
  char dummy;

  if (zones != NULL)
    Error("already loaded!");

  f = fopen(filename, "rb");
  if (f == NULL)
    {
      int x, y;
      memset(&header, 0, sizeof(header));
      header.magic = MAGIC;
      header.zone_width = ZONE_WIDTH;
      header.zone_height = ZONE_HEIGHT;
      header.zone_size = ZONE_SIZE;
      header.numzones = 0;
      header.curzx = 0;
      header.curzy = 0;
      x = ZONE_WIDTH / 2;
      y = ZONE_HEIGHT / 2;
      header.curp = x * ZONE_HEIGHT + y;
      header.curdir = 0;
      Log("*** STARTING ***");
    }
  else
    {
      readall(f, &header, sizeof(header));
      if (header.magic != MAGIC)
        Error("bad MAGIC in file");
      printf("loading %s... width=%d, height=%d, size=%d, numzones=%d\n",
             filename,
             header.zone_width,
             header.zone_height,
             header.zone_size,
             header.numzones);
      if (header.zone_width != ZONE_WIDTH ||
          header.zone_height != ZONE_HEIGHT ||
          header.zone_size != ZONE_SIZE)
        Error("wrong zone size in the file, recompile " __FILE__);

      for (i=0; i<header.numzones; i++)
        {
          struct zone_s *zp = malloc(sizeof(struct zone_s));
          if (zp == NULL)
            Error("cannot allocate enough memory to load the file");
          memset(zp, 0, sizeof(struct zone_s) - sizeof(zonedata_t));
          readall(f, &zp->z, sizeof(zonedata_t));
          zp->next = zones;
          zones = zp;
        }

      if (fread(&dummy, 1, 1, f) != 0)
        Error("too much data in file");
      fclose(f);
      Log("*** RESUMING ***");
    }
  lastsync = time(NULL);
}

void check_ending_conditions(void)
{
  if (stopflag < 0)
    ;
  else if (header.numzones >= STOP_AT_N_ZONES)
    {
      Log("*** STOP_AT_N_ZONES ***");
      stopflag = -1;
    }
  else if (time(NULL) - lastsync >= SAVE_EVERY_N_SECONDS)
    {
      Log("*** Auto-save ***");
      stopflag = -2;
    }
}

struct zone_s *allocatezone(int zx, int zy)
{
  int i;
  struct zone_s* zp;

  Log("new zone #%d (%d,%d)", header.numzones, zx, zy);
  zp = malloc(sizeof(struct zone_s));
  if (zp == NULL)
    Error("out of memory");
  memset(zp, 0, sizeof(struct zone_s));
  zp->z.zx = zx;
  zp->z.zy = zy;
  zp->z.creation_time = (uint32) time(NULL);
  for (i=0; i<ZONE_HEIGHT; i++)
    {
      zp->z.data[i] = 243;
      zp->z.data[i + (ZONE_WIDTH-1)*ZONE_HEIGHT] = 243;
    }
  for (i=0; i<ZONE_WIDTH; i++)
    {
      zp->z.data[i*ZONE_HEIGHT] = 243;
      zp->z.data[i*ZONE_HEIGHT + ZONE_HEIGHT-1] = 243;
    }
  zp->next = zones;
  zones = zp;
  header.numzones++;
  return zp;
}

struct zone_s *findzone(int zx, int zy)
{
  struct zone_s *zp;
  for (zp = zones; zp; zp = zp->next)
    if (zp->z.zx == zx && zp->z.zy == zy)
      return zp;
  return allocatezone(zx, zy);
}

struct zone_s *walk_to_adj_zone(struct zone_s *zp, int dx, int dy)
{
  struct zone_s *result = findzone(zp->z.zx + dx, zp->z.zy + dy);
  if (dx == -1 && dy == 0) zp->left  = result;
  if (dx == +1 && dy == 0) zp->right = result;
  if (dy == -1 && dx == 0) zp->above = result;
  if (dy == +1 && dx == 0) zp->below = result;
  check_ending_conditions();
  return result;
}

/************************************************************/

unsigned char table1[24*512];

#define P_OFFSET(dir)  (*(long*)(table1 + (dir) + 2*244))

#define INITENTRY(indir, inbyte, outdir, outbyte)               \
		(*(short*)(table1 + 512*(indir) + 2*(inbyte)) = \
		 512*(outdir) + (outbyte))

void maketables(void)
{
  int i, dir;
  static int p_offset[12] = { -ZONE_HEIGHT,   /* enter bit 0 from the left */
                              +ZONE_HEIGHT,   /* enter bit 4 from the right */
                              +1, +1, +1, +1, +1,   /* enter from above */
                              -1, -1, -1, -1, -1 }; /* enter from below */
  static int p_newbit[12] = { 0, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4 };
  static int p_pow3[5] = { 1, 3, 9, 27, 81 };

  for (dir=0; dir<12; dir++)
    {
      P_OFFSET(512*dir) = p_offset[dir];
      INITENTRY(dir, 243, dir+12, 243);

      for (i=0; i<243; i++)
        {
          int byte = i;
          int d = p_offset[dir];
          int n = p_newbit[dir];
          int newdir;
          while (1)
            {
              /* turn left by default */
              switch (d)
                {
                case -ZONE_HEIGHT: d = +1;           break;
                case +1:           d = +ZONE_HEIGHT; break;
                case +ZONE_HEIGHT: d = -1;           break;
                case -1:           d = -ZONE_HEIGHT; break;
                }
              if ((byte / p_pow3[n]) % 3 == 0)
                {
                  /* should have turned right */
                  d = -d;
                  byte += 2 * p_pow3[n];
                }
              else
                {
                  byte -= p_pow3[n];
                }
              if (d == 1 || d == -1)
                break;
              if (d < 0)
                n += 1;
              else
                n -= 1;
              if (n < 0 || n >= 5)
                break;
            }

          if (n < 0)
            newdir = 1;
          else if (n >= 5)
            newdir = 0;
          else if (d > 0)
            newdir = 2 + n;
          else
            newdir = 7 + n;

          INITENTRY(dir, i, newdir, byte);
        }
    }

  for (dir=12; dir<24; dir++)
    {
      P_OFFSET(512*dir) = 0;
      INITENTRY(dir, 243, dir, 243);
      for (i=0; i<243; i++)
        INITENTRY(dir, i, -1, i);   /* bogus entry: "don't use me" */
    }

#ifdef DUMPTABLES
  for (dir=0; dir<12; dir++)
    {
      printf("P_OFFSET(0x%x) = %d\n", dir, P_OFFSET(512*dir));
      for (i=0; i<243; i++)
        printf("[%03x]", (int) *(short*)(table1 + 512*dir + 2*i));
      printf("\n");
    }
#endif
}

#define LOOPBODY                                \
  p += P_OFFSET(dir);                           \
  dir = *(short*)(table1 + dir + 2*(long)(*p)); \
  *p = (unsigned char) dir;                     \
  dir &= -256;

/* the next bit of assembler is not used, because GCC produces almost
   the same thing from the C code of LOOPBODY anyway */
#define LOOPBODY2                               \
  asm volatile ("                             \n\
	addl	table1+488(%%ebx), %%edx      \n\
	movzbl	(%%edx), %%eax                \n\
	movzwl	table1(%%ebx,%%eax,2), %%ebx  \n\
	movb	%%bl, (%%edx)                 \n\
	andl	$-256, %%ebx"                   \
      : "=d" (p), "=b" (dir)                    \
      :  "0" (p),  "1" (dir)                    \
      : "eax" );

#define WALK_TO_ADJ_ZONE(dirname, dx, dy)                               \
	zp = (zp->dirname ? zp->dirname : walk_to_adj_zone(zp, dx, dy))


void run(void)
{
  struct zone_s *zp = findzone(header.curzx, header.curzy);
  long curp = header.curp;
  long dir = header.curdir;
  unsigned char *p = zp->z.data + curp;

 restart:
  do
    {
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
      LOOPBODY
    }
  while (dir < stopflag);

  curp = p - zp->z.data;

  /* slow path: walking over to an adjacent zone */
  switch (dir / 512) {

  case 12:    /* left */
    WALK_TO_ADJ_ZONE(left, -1, 0);
    curp += (ZONE_WIDTH-1) * ZONE_HEIGHT;
    break;

  case 13:    /* right */
    WALK_TO_ADJ_ZONE(right, +1, 0);
    curp -= (ZONE_WIDTH-1) * ZONE_HEIGHT;
    break;

  case 14:
  case 15:
  case 16:
  case 17:
  case 18:    /* down */
    WALK_TO_ADJ_ZONE(below, 0, +1);
    curp -= (ZONE_HEIGHT-1);
    break;

  case 19:
  case 20:
  case 21:
  case 22:
  case 23:    /* up */
    WALK_TO_ADJ_ZONE(above, 0, -1);
    curp += (ZONE_HEIGHT-1);
    break;

  default:    /* dir < 12, which implies that 'stopflag' has been changed */
    header.curzx = zp->z.zx;
    header.curzy = zp->z.zy;
    header.curp = curp;
    header.curdir = dir;
    return;
  }

  dir -= 12*512;
  p = zp->z.data + curp;
  goto restart;
}

/************************************************************/

static void myhandler(int ignored)
{
  stopflag = -1;
}

static void mysynchandler(int ignored)
{
  if (stopflag != -1)
    stopflag = -2;
}

static void mythumbhandler(int ignored)
{
  if (stopflag != -1)
    stopflag = -3;
}

void install_sighandler(void)
{
  if (signal(SIGINT, &myhandler) == SIG_ERR ||
      signal(SIGTERM, &myhandler) == SIG_ERR ||
      signal(SIGHUP, &mysynchandler) == SIG_ERR ||
      signal(SIGUSR1, &mythumbhandler) == SIG_ERR ||
      signal(SIGPIPE, SIG_IGN) == SIG_ERR)
    PError("cannot install signal handlers");
}

void write_pid_file(void)
{
  pid_t pid;
  FILE *f = fopen(PID_FILE, "w");
  if (f == NULL)
    PError("cannot write to " PID_FILE);
  pid = getpid();
  fprintf(f, "%ld\n", (long)pid);
  fclose(f);
}

void remove_pid_file(void)
{
  unlink(PID_FILE);
}

/************************************************************/

int main(int argc, char** argv)
{
  check_assertions();
  maketables();
  load(DUMP_FILE);
  install_sighandler();
  write_pid_file();
  while (1)
    {
      stopflag = 12*512;
      run();
      if (stopflag != -3)
        save(DUMP_FILE);
      save_thumb(THUMB_FILE);
      if (stopflag == -1)
        break;
    }
  Log("*** SHUTDOWN ***");
  remove_pid_file();
  return 0;
}