/* DLIFE Copyright (C) 2000 Richard W.M. Jones <rich@annexia.org>
 * and other authors listed in the ``AUTHORS'' file.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * $Id: exec.c,v 1.2 2002/04/05 16:47:12 rich Exp $
 */

#include "config.h"

#include <stdio.h>

#include "cell.h"
#include "random.h"
#include "params.h"
#include "soup.h"

#define TRACE 0

#if TRACE
static void trace (const struct cell *cell, int insn);
#endif

unsigned long long cell_cycle = 0;

static inline int
get_pattern_length (struct state *state, const struct cell *cell)
{
  int p = cell->p;
  int c;

  /* XXX Maximum pattern length? */
  /* XXX What if pattern exceeds limits of the cell? */
  while ((c = get_soup (state, cell->frag, p) & 0x3F) == 0 || c == 1)
    {
      p++;
    }

  return p - cell->p;
}

static inline int
check_access (struct state *state, const struct cell *cell, reg_t raddr)
{
  if (raddr >= 0 && raddr < cell->frag->len) /* In mother? */
    return 1;
  if (cell->daughter)		/* In daughter? */
    {
      int offset = cell->daughter->frag->base - cell->frag->base;

      /* Be careful with the wrap-around case here. */
      if (((raddr - offset) & (state->soup_size - 1)) >= 0 &&
	  ((raddr - offset) & (state->soup_size - 1)) < cell->daughter->frag->len)
	return 1;
    }
  return 0;
}

static inline int
check_exec_access (struct state *state, const struct cell *cell, reg_t raddr)
{
  if (raddr >= 0 && raddr < cell->frag->len) /* In mother? */
    return 1;
  return 0;
}

static inline void
push (struct cell *cell, reg_t v)
{
  cell->sp = (cell->sp+1) & (STACK_SIZE-1);
  cell->stack[cell->sp] = v;
}

static inline void
pop (struct cell *cell, reg_t *va)
{
  *va = cell->stack[cell->sp];
  cell->sp = (cell->sp-1) & (STACK_SIZE-1);
}

void
exec_insn (struct state *state, struct cell *cell)
{
  /* Increment cycle counters. */
  state->cell_cycle++;
  cell->cycle++;

  /* State? */
  if (cell->state == state_exec)
    {
      int insn, error;

    next:
      /* Fetch next insn. */
      if (check_exec_access (state, cell, cell->p) ||
	  chance (access_control_failure))
	{
	  insn = get_soup (state, cell->frag, cell->p);
	}
      else
	{
	  INC_ERRORS (state, cell);

	  /* Increment PC */
	  cell->p++;

	  return;
	}

      /* By doing this we allow the cell to use the top two bits of
       * each instruction byte for its own purposes. DNA uses a similar
       * technique - it can mark up basic sequences by adding its
       * own arbitrary chemical markers to each base.
       */
      insn &= 0x3f;

#if TRACE
      trace (cell, insn);
#endif

      if (chance (soup_fetch_failure))
	{
	  insn = get_rand_byte () & 0x3f;
	}

      /* Increment PC */
      if (!chance (inc_pc_failure))
	{
	  cell->p++;
	}

      /* Is this insn going to generate an error? Handle that case
       * separately (don't disturb the fast path).
       */
      error = chance (insn_exec_failure);

      if (!error)
	{
	  switch (insn)
	    {
	    case 0:		/* NOP0 */
	    case 1:		/* NOP1 */
	      return;		/* Ignore. */
	    case 2:		/* INC A */
	      cell->a++;
	      return;
	    case 3:		/* DEC A */
	      cell->a--;
	      return;
	    case 4:		/* SHL A */
	      cell->a <<= 1;
	      return;
	    case 7:		/* IFZ */
	      if (cell->a == 0)
		goto next;	/* Fetch and execute next instruction. */
	      /* Else skip next insn. */
	      cell->p++;
	      return;
	    case 8:		/* FINDB */
	      if ((cell->plen = get_pattern_length (state, cell)) > 0)
		{
		  cell->state = state_find;
		  cell->dir = -1;
		  cell->i = cell->p - 2;
		  cell->lim = FIND_LENGTH_LIMIT;
		}
	      else
		{
		  INC_ERRORS (state, cell);
		  cell->i = 0;
		}
	      return;
	    case 9:		/* FINDF */
	      if ((cell->plen = get_pattern_length (state, cell)) > 0)
		{
		  cell->state = state_find;
		  cell->dir = 1;
		  cell->i = cell->p + cell->plen + 1;
		  cell->lim = FIND_LENGTH_LIMIT;
		}
	      else
		{
		  INC_ERRORS (state, cell);
		  cell->i = 0;
		}
	      return;
	    case 0x0a:		/* MALLOC */
	      if (!cell->daughter &&
		  cell->a >= MIN_CELL_SIZE && cell->a <= MAX_CELL_SIZE)
		{
		  struct soup_frag *frag
		    = soup_frag_malloc (state, cell->frag, cell->a);
		  if (frag)
		    {
		      cell->daughter
			= cell_malloc (state, cell, frag);
		      /* Calculate relative address of daughter */
		      cell->i
			= cell->daughter->frag->base
			- cell->frag->base;
#if 0
		      printf ("MALLOC: dfb = %d, fb = %d, i = %d\n",
			      cell->daughter->frag->base,
			      cell->frag->base,
			      cell->i);
#endif
		    }
		  else
		    {
		      /* INC_ERRORS (state, cell); -- Dubious? */
		      cell->i = 0;
		    }
		}
	      else
		{
		  INC_ERRORS (state, cell);
		  cell->i = 0;
		}
	      return;
	    case 0x0b:		/* DIVIDE */
	      if (cell->daughter)
		{
		  cell_divide (state, cell, cell->daughter);
		  cell_activate (state, cell->daughter);
		  cell->daughter = 0;
		}
	      else
		{
		  INC_ERRORS (state, cell);
		  cell->i = 0;
		}
	      return;
	    case 0x0c:		/* MOVE [I],A */
	      cell->a = get_soup (state, cell->frag, cell->i);
	      return;
	    case 0x0d:		/* MOVE A,[I] */
	      if (check_access (state, cell, cell->i) ||
		  chance (access_control_failure))
		{
		  set_soup (state, cell->frag, cell->a, cell->i);
		}
	      else
		{
		  INC_ERRORS (state, cell);
		}
	      return;
	    case 0x0e:		/* DMOVE [I],A */
	      cell->a = get_soup (state, cell->frag, cell->i) << 8;
	      cell->a |= get_soup (state, cell->frag, cell->i+1);
	      return;
	    case 0x0f:		/* DMOVE A,[I] */
	      if ((check_access (state, cell, cell->i) &&
		   check_access (state, cell, cell->i+1)) ||
		  chance (access_control_failure))
		{
		  set_soup (state, cell->frag, cell->a >> 8, cell->i);
		  set_soup (state, cell->frag, cell->a & 0xff, cell->i+1);
		}
	      else
		{
		  INC_ERRORS (state, cell);
		}
	      return;
	    case 0x10:		/* XOR A,A (ie. ZERO A) */
	      cell->a = 0; return;
	    case 0x11:		/* XOR B,A */
	      cell->a ^= cell->b; return;
	    case 0x12:		/* XOR I,A */
	      cell->a ^= cell->i; return;
	    case 0x13:		/* XOR P,A */
	      cell->a ^= cell->p; return;
	    case 0x14:		/* XOR A,B */
	      cell->b ^= cell->a; return;
	    case 0x15:		/* XOR B,B (ie. ZERO B) */
	      cell->b = 0; return;
	    case 0x16:		/* XOR I,B */
	      cell->b ^= cell->i; return;
	    case 0x17:		/* XOR P,B */
	      cell->b ^= cell->p; return;
	    case 0x18:		/* XOR A,I */
	      cell->i ^= cell->a; return;
	    case 0x19:		/* XOR B,I */
	      cell->i ^= cell->b; return;
	    case 0x1a:		/* XOR I,I (ie. ZERO I) */
	      cell->i = 0; return;
	    case 0x1b:		/* XOR P,I */
	      cell->i ^= cell->p; return;
	      /* Surely these next three instructions will never be used ... */
	    case 0x1c:		/* XOR A,P */
	      cell->p ^= cell->a; return;
	    case 0x1d:		/* XOR B,P */
	      cell->p ^= cell->b; return;
	    case 0x1e:		/* XOR I,P */
	      cell->p ^= cell->i; return;
	    case 0x1f:		/* XOR P,P (ie. ZERO P) */
	      cell->p = 0; return;
	    case 0x20:		/* PUSH A */
	      push (cell, cell->a);
	      return;
	    case 0x21:		/* PUSH B */
	      push (cell, cell->b);
	      return;
	    case 0x22:		/* PUSH I */
	      push (cell, cell->i);
	      return;
	    case 0x23:		/* PUSH P */
	      push (cell, cell->p);
	      return;
	    case 0x24:		/* POP A */
	      pop (cell, &cell->a);
	      return;
	    case 0x25:		/* POP B */
	      pop (cell, &cell->b);
	      return;
	    case 0x26:		/* POP I */
	      pop (cell, &cell->i);
	      return;
	    case 0x27:		/* POP P */
	      pop (cell, &cell->p);
	      return;

	    default:		/* Unknown instruction. */
	      INC_ERRORS (state, cell);
	      return;
	    }
	}
      else
	{
	  /* Slow path: insn will execute in error. */
	  switch (insn)
	    {
	    case 2:		/* INC A */
	      if (chance (2))
		cell->a += 2;
	      return;
	    case 3:		/* DEC A */
	      if (chance (2))
		cell->a -= 2;
	      return;
	    case 4:		/* SHL A */
	      if (chance (2))
		cell->a <<= 2;
	      return;
	    case 7:		/* IFZ */
	      if (chance (2))
		goto next;	/* Fetch and execute next instruction. */
	      /* Else skip next insn. */
	      cell->p++;
	      return;
	    case 8:		/* FINDB */
	      if (chance (2))
		cell->i = 0;
	      return;
	    case 9:		/* FINDF */
	      if (chance (2))
		cell->i = 0;
	      return;
	    case 0x0c:		/* MOVE [I],A */
	      cell->a = get_soup (state, cell->frag, cell->i);
	      if (chance (2))
		cell->a++;
	      else
		cell->a--;
	      return;
	    case 0x0d:		/* MOVE A,[I] */
	      {
		int i = chance (4);
		switch (i)
		  {
		  case 0:
		    set_soup (state, cell->frag, cell->a+1, cell->i);
		    return;
		  case 1:
		    set_soup (state, cell->frag, cell->a-1, cell->i);
		    return;
		  case 2:
		    set_soup (state, cell->frag, cell->a, cell->i+1);
		    return;
		  case 3:
		    set_soup (state, cell->frag, cell->a, cell->i-1);
		    return;
		  }
		return;
	      }
	    case 0x0e:		/* DMOVE [I],A */
	      cell->a = get_soup (state, cell->frag, cell->i) << 8;
	      cell->a |= get_soup (state, cell->frag, cell->i+1);
	      if (chance (2))
		cell->a++;
	      else
		cell->a--;
	      return;
	    case 0x0f:		/* DMOVE A,[I] */
	      {
		int i = chance (4);
		switch (i)
		  {
		  case 0:
		    set_soup (state, cell->frag, (cell->a+1) >> 8, cell->i);
		    set_soup (state, cell->frag, (cell->a+1) & 0xFF, cell->i+1);
		    return;
		  case 1:
		    set_soup (state, cell->frag, (cell->a-1) >> 8, cell->i);
		    set_soup (state, cell->frag, (cell->a-1) & 0xFF, cell->i+1);
		    return;
		  case 2:
		    set_soup (state, cell->frag, cell->a >> 8, cell->i+1);
		    set_soup (state, cell->frag, cell->a & 0xFF, cell->i+2);
		    return;
		  case 3:
		    set_soup (state, cell->frag, cell->a >> 8, cell->i-1);
		    set_soup (state, cell->frag, cell->a & 0xFF, cell->i);
		    return;
		  }
		return;
	      }
	    case 0x10:		/* XOR ... */
	      return;
	    case 0x11:
	      cell->a = cell->b; return;
	    case 0x12:
	      cell->a = cell->i; return;
	    case 0x13:
	      cell->a = cell->p; return;
	    case 0x14:
	      cell->b = cell->a; return;
	    case 0x15:
	      return;
	    case 0x16:
	      cell->b = cell->i; return;
	    case 0x17:
	      cell->b = cell->p; return;
	    case 0x18:
	      cell->i = cell->a; return;
	    case 0x19:
	      cell->i = cell->b; return;
	    case 0x1a:
	      return;
	    case 0x1b:
	      cell->i = cell->p; return;
	    case 0x1c:
	      cell->p = cell->a; return;
	    case 0x1d:
	      cell->p = cell->b; return;
	    case 0x1e:
	      cell->p = cell->i; return;
	    case 0x1f:
	      return;
	    }
	}
    }
  else /* cell->state == state_find */
    {
      /* During finds,
       * cell->p     == address of pattern complement to match
       * cell->plen  == length of pattern
       * cell->i     == current address of search
       * cell->dir   == direction of search (-1 or 1)
       * cell->lim   == number of steps before we give up
       */
      int i;

#if TRACE
      trace (cell, -1);
#endif

      for (i = 0; i < cell->plen; ++i)
	{
	  int pat = get_soup (state, cell->frag, cell->p+i);
	  int mat = get_soup (state, cell->frag, cell->i+i);
	  if (pat > 1 || mat > 1 || pat == mat)
	    {
	      /* Not matched: continue searching. */
	      cell->i += cell->dir;
	      cell->lim--;
	      if (cell->lim == 0)
		{
		  /* Give up. */
		  cell->i = 0;
		  INC_ERRORS (state, cell);
		  cell->state = state_exec;
		  cell->p += cell->plen;
		  return;
		}
	      return;
	    }
	} /* for */

      /* Pattern matched! */
      cell->p += cell->plen;
      cell->state = state_exec;
      return;
    }
}

#if TRACE
static void
trace (const struct cell *cell, int insn)
{
  if (cell->state == state_exec)
    {
      printf ("x %p A:%d B:%d I:%d P:%d St:[%d %d %d..] e:%d [%p] ",
	      cell, cell->a, cell->b, cell->i, cell->p,
	      cell->stack[cell->sp],
	      cell->stack[(cell->sp-1) & (STACK_SIZE-1)],
	      cell->stack[(cell->sp-2) & (STACK_SIZE-1)],
	      cell->errors,
	      cell->daughter);
      switch (insn)
	{
	case 0: printf ("NOP0"); break;
	case 1: printf ("NOP1"); break;
	case 2: printf ("INC A"); break;
	case 3: printf ("DEC A"); break;
	case 4: printf ("SHL A"); break;
	case 7: printf ("IFZ"); break;
	case 8: printf ("FINDB"); break;
	case 9: printf ("FINDF"); break;
	case 10: printf ("MALLOC"); break;
	case 11: printf ("DIVIDE"); break;
	case 12: printf ("MOVE [I],A"); break;
	case 13: printf ("MOVE A,[I]"); break;
	case 14: printf ("DMOVE [I],A"); break;
	case 15: printf ("DMOVE A,[I]"); break;
	case 16: case 17: case 18: case 19:
	case 20: case 21: case 22: case 23:
	case 24: case 25: case 26: case 27:
	case 28: case 29: case 30: case 31:
	  printf ("XOR %c,%c", "ABIP"[insn&3], "ABIP"[(insn>>2)&3]); break;
	case 32: case 33: case 34: case 35:
	  printf ("PUSH %c", "ABIP"[insn&3]); break;
	case 36: case 37: case 38: case 39:
	  printf ("POP %c", "ABIP"[insn&3]); break;
	default: printf ("unknown %d", insn); break;
	}
      printf ("\n");
    }
  else
    {
      printf ("f %p I:%d P:%d dir:%d plen:%d lim:%d\n",
	      cell, cell->i, cell->p, cell->dir, cell->plen, cell->lim);
    }
}
#endif