/***

gcc -march=pentium-m -mtune=pentium-m -O3 -fno-reorder-blocks direct3_fourmis.c

On my 1733 MHz Pentium M laptop, this runs at ~ 174000000 ant steps per second

 ***/

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <stdarg.h>
#include <time.h>
#include <signal.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/mman.h>

#define FILENAME      "Areas"
#define LOG_FILENAME  "areas.log"

#define COUNT_STEPS

typedef int int32;
#define PAGESIZE     4096

//#define HEIGHT       96931       /* prime number */
//#define HEIGHT       10003
#define HEIGHT       9700
#define WIDTH        (HEIGHT/5)
#define TOTALSIZE    (((long) WIDTH) * ((long) HEIGHT))

typedef struct {
  int32 width, height;
  int32 next_x, next_y;
} header_t;

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_FILENAME, "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 check_assertions(void)
{
  printf("source code:    %s\n", __FILE__);
  printf("board width:    %d pixels (%d columns)\n", WIDTH*5, WIDTH);
  printf("board height:   %d pixels\n", HEIGHT);
  printf("total size:     %ld MB\n", (long)(TOTALSIZE/(1024*1024)));
#ifdef COUNT_STEPS
  printf("COUNTING STEPS\n");
#endif
}

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

unsigned char *Data;
int Data_fd;
long next_x, next_y;

void load(void)
{
  off_t Data_length;
  Data_fd = open(FILENAME, O_RDWR | O_CREAT, 0644);
  if (Data_fd == -1)
    Error("open failed");
  Data_length = lseek(Data_fd, 0, SEEK_END);
  if (Data_length == 0)
    {
      header_t header;
      Log("*** STARTING ***");
      header.width = WIDTH;
      header.height = HEIGHT;
      header.next_x = WIDTH/2;
      header.next_y = HEIGHT/2;
      if (write(Data_fd, &header, sizeof(header)) != sizeof(header))
        Error("write failed");
      if (ftruncate(Data_fd, TOTALSIZE) < 0)
        Error("ftruncate failed");
      Data_length = lseek(Data_fd, 0, SEEK_END);
    }
  else
    Log("*** RESUMING ***");
  if (Data_length != TOTALSIZE)
    Error("bogus file length");
  lseek(Data_fd, 0, SEEK_SET);

  Data = mmap(NULL, TOTALSIZE,
              PROT_READ | PROT_WRITE,
              MAP_SHARED, Data_fd, 0);
  if (Data == MAP_FAILED)
    Error("mmap failed");

  {
    long x, offset;
    if (mprotect(Data + PAGESIZE, HEIGHT - PAGESIZE, PROT_NONE) < 0)
      Error("mprotect[1] failed");
    offset = TOTALSIZE - HEIGHT;
    offset &= ~(PAGESIZE-1);
    if (mprotect(Data + offset, TOTALSIZE - offset, PROT_NONE) < 0)
      Error("mprotect[2] failed");
    for (x=1; x<WIDTH; x++)
      {
        offset = x * (long) HEIGHT;
        offset &= ~(PAGESIZE-1);
        if (mprotect(Data + offset, PAGESIZE, PROT_NONE) < 0)
          Error("mprotect[3] failed");
      }
  }

  {
    header_t *headerp = (header_t*) Data;
    if (headerp->width != WIDTH)
      Error("bogus header->width");
    if (headerp->height != HEIGHT)
      Error("bogus header->height");
    next_x = headerp->next_x;
    next_y = headerp->next_y;
    if (next_x < 0 || next_y < 0)
      Error("No valid next position");
    headerp->next_x = -1;
    headerp->next_y = -1;
  }
}

void save(void)
{
  header_t *headerp = (header_t*) Data;
  headerp->next_x = next_x;
  headerp->next_y = next_y;
  Log("*** SHUTTING DOWN ***");
}

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

volatile int stopflag = 0;

#ifdef COUNT_STEPS
volatile long long steps = 0;
#  define STEP  steps++,
#else
#  define STEP  /* nothing */
#endif

#define ZERO_0   (STEP table1[byte] & 1)
#define ZERO_1   (STEP table1[byte] & 2)
#define ZERO_2   (STEP table1[byte] & 4)
#define ZERO_3   (STEP table1[byte] & 8)
#define ZERO_4   (STEP byte < 81)

#define PZERO_0   (STEP table1[pbyte] & 1)
#define PZERO_1   (STEP table1[pbyte] & 2)
#define PZERO_2   (STEP table1[pbyte] & 4)
#define PZERO_3   (STEP table1[pbyte] & 8)
#define PZERO_4   (STEP pbyte < 81)

#define TRBIT_0        1
#define TRBIT_1        3
#define TRBIT_2        9
#define TRBIT_3        27
#define TRBIT_4        81

unsigned char table1[243];

void maketables(void)
{
  int i;
  for (i=0; i<243; i++)
    {
      unsigned char c = 0;
      if ((i / 1)  % 3 == 0) c |= 1;
      if ((i / 3)  % 3 == 0) c |= 2;
      if ((i / 9)  % 3 == 0) c |= 4;
      if ((i / 27) % 3 == 0) c |= 8;
      table1[i] = c;
    }
}

#define GOLEFT    (*p = byte, p -= HEIGHT, byte = *p)
#define GORIGHT   (*p = byte, p += HEIGHT, byte = *p)
#define GOUP      (*p = byte, p--, byte = *p)
#define GODOWN    (*p = byte, p++, byte = *p)

#define GEN(bl, br)                             \
     left_from_##br:                            \
       byte += 2 * TRBIT_##br;                  \
       if (bl == 0 && stopflag) goto escape;    \
     close_loop_##br:                           \
       if (bl == 0) GOLEFT;                     \
       if (ZERO_##bl) goto up_from_##bl;        \
       byte -= 3 * TRBIT_##bl;                  \
     down_from_##bl:                            \
       byte += 2 * TRBIT_##bl;                  \
       GODOWN;                                  \
       if (ZERO_##bl) goto left_from_##bl;      \
       byte -= 3 * TRBIT_##bl;                  \
     right_from_##bl:                           \
       byte += 2 * TRBIT_##bl;                  \
       if (bl == 0) GORIGHT;                    \
       if (ZERO_##br) goto down_from_##br;      \
       byte -= 3 * TRBIT_##br;                  \
     up_from_##br:                              \
       byte += 2 * TRBIT_##br;                  \
       GOUP;                                    \
       if (ZERO_##br) goto right_from_##br;     \
       byte -= TRBIT_##br;                      \
       goto close_loop_##br

#define GEN2(bl, br)                                                     \
     close_##br:                                                        \
       byte -= TRBIT_##br;                                              \
       if (bl == 0 && stopflag) goto escape;                            \
     close_loop_##br:                                                   \
     left_from_##br:                                                    \
       if (bl == 0) GOLEFT;                                             \
       if (ZERO_##bl) { byte += 2 * TRBIT_##bl; goto up_from_##bl; }    \
       byte -= TRBIT_##bl;                                              \
     down_from_##bl:                                                    \
       GODOWN;                                                          \
       if (ZERO_##bl) { byte += 2 * TRBIT_##bl; goto left_from_##bl; }  \
       byte -= TRBIT_##bl;                                              \
     right_from_##bl:                                                   \
       if (bl == 0) GORIGHT;                                            \
       if (ZERO_##br) { byte += 2 * TRBIT_##br; goto down_from_##br; }  \
       byte -= TRBIT_##br;                                              \
     up_from_##br:                                                      \
       GOUP;                                                            \
       if (ZERO_##br) { byte += 2 * TRBIT_##br; goto right_from_##br; } \
       goto close_##br

#define GEN3(bl, br)                                                     \
     close_loop_##br:                                                   \
     left_from_##br:                                                    \
       if (bl == 0) GOLEFT;                                             \
       if (!ZERO_##bl) { byte -= TRBIT_##bl; goto down_from_##bl; }     \
       byte += 2 * TRBIT_##bl;                                          \
     up_from_##bl:                                                      \
       GOUP;                                                            \
       if (!ZERO_##bl) { byte -= TRBIT_##bl; goto left_from_##bl; }     \
       byte += 2 * TRBIT_##bl;                                          \
     right_from_##bl:                                                   \
       if (bl == 0) GORIGHT;                                            \
       if (!ZERO_##br) { byte -= TRBIT_##br; goto up_from_##br; }       \
       byte += 2 * TRBIT_##br;                                          \
     down_from_##br:                                                    \
       GODOWN;                                                          \
       if (!ZERO_##br) { byte -= TRBIT_##br; goto right_from_##br; }    \
       byte += 2 * TRBIT_##br;                                          \
       if (bl == 0 && stopflag) goto escape;                            \
       goto left_from_##br

#define GEN4(bl, br)                             \
     left_from_##br:                            \
       byte += 2 * TRBIT_##br;                  \
       if (bl == 0 && stopflag) goto escape;    \
     close_loop_##br:                           \
       if (bl == 0) { GOLEFT; pbyte=byte; }     \
       if (PZERO_##bl) goto up_from_##bl;       \
       byte -= 3 * TRBIT_##bl;                  \
     down_from_##bl:                            \
       byte += 2 * TRBIT_##bl;                  \
       GODOWN;                                  \
       if (ZERO_##bl) { pbyte=byte; goto left_from_##bl; } \
       pbyte = byte;                            \
       byte -= 3 * TRBIT_##bl;                  \
     right_from_##bl:                           \
       byte += 2 * TRBIT_##bl;                  \
       if (bl == 0) { GORIGHT; pbyte=byte; }    \
       if (PZERO_##br) goto down_from_##br;     \
       byte -= 3 * TRBIT_##br;                  \
     up_from_##br:                              \
       byte += 2 * TRBIT_##br;                  \
       GOUP;                                    \
       if (ZERO_##br) { pbyte=byte; goto right_from_##br; } \
       pbyte = byte;                                        \
       byte -= TRBIT_##br;                      \
       goto close_loop_##br


void run(void)
{
  unsigned char *p = Data + next_x * HEIGHT + next_y;
  int byte = *p;
  //int pbyte = byte;
  goto close_loop_4;

  GEN(0, 4);
  GEN(4, 3);
  GEN(3, 2);
  GEN(2, 1);
  GEN(1, 0);

 escape:
  *p = byte;
  next_x = (p - Data) / HEIGHT;
  next_y = (p - Data) % HEIGHT;
}

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

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

static void mysynchandler(int ignored)
{
  stopflag = 2;
}

static void mysegvhandler(int ignored)
{
#ifdef COUNT_STEPS
  fprintf(stderr, "Number of steps: %lld\n", steps);
#endif
  Error("SIGSEGV");
}

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

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

int main(int argc, char** argv)
{
  check_assertions();
  maketables();
  install_sighandler();
  load();
  while (1)
    {
      run();
#ifdef COUNT_STEPS
      fprintf(stderr, "Number of steps: %lld\n", steps);
#endif
      if (stopflag == 1)
        break;
      stopflag = 0;
      msync(Data, TOTALSIZE, MS_ASYNC | MS_INVALIDATE);
      Log("*** Sync ***    ");
    }
  save();
  return 0;
}