exec.c

   1 /* DLIFE Copyright (C) 2000 Richard W.M. Jones <rich@annexia.org>
   2  * and other authors listed in the ``AUTHORS'' file.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  17  *
  18  * $Id: exec.c,v 1.2 2002/04/05 16:47:12 rich Exp $
  19  */
  20
  21 #include "config.h"
  22
  23 #include <stdio.h>
  24
  25 #include "cell.h"
  26 #include "random.h"
  27 #include "params.h"
  28 #include "soup.h"
  29
  30 #define TRACE 0
  31
  32 #if TRACE
  33 static void trace (const struct cell *cell, int insn);
  34 #endif
  35
  36 unsigned long long cell_cycle = 0;
  37
  38 static inline int
  39 get_pattern_length (struct state *state, const struct cell *cell)
  40 {
  41   int p = cell->p;
  42   int c;
  43
  44   /* XXX Maximum pattern length? */
  45   /* XXX What if pattern exceeds limits of the cell? */
  46   while ((c = get_soup (state, cell->frag, p) & 0x3F) == 0 || c == 1)
  47     {
  48       p++;
  49     }
  50
  51   return p - cell->p;
  52 }
  53
  54 static inline int
  55 check_access (struct state *state, const struct cell *cell, reg_t raddr)
  56 {
  57   if (raddr >= 0 && raddr < cell->frag->len) /* In mother? */
  58     return 1;
  59   if (cell->daughter)           /* In daughter? */
  60     {
  61       int offset = cell->daughter->frag->base - cell->frag->base;
  62
  63       /* Be careful with the wrap-around case here. */
  64       if (((raddr - offset) & (state->soup_size - 1)) >= 0 &&
  65           ((raddr - offset) & (state->soup_size - 1)) < cell->daughter->frag->len)
  66         return 1;
  67     }
  68   return 0;
  69 }
  70
  71 static inline int
  72 check_exec_access (struct state *state, const struct cell *cell, reg_t raddr)
  73 {
  74   if (raddr >= 0 && raddr < cell->frag->len) /* In mother? */
  75     return 1;
  76   return 0;
  77 }
  78
  79 static inline void
  80 push (struct cell *cell, reg_t v)
  81 {
  82   cell->sp = (cell->sp+1) & (STACK_SIZE-1);
  83   cell->stack[cell->sp] = v;
  84 }
  85
  86 static inline void
  87 pop (struct cell *cell, reg_t *va)
  88 {
  89   *va = cell->stack[cell->sp];
  90   cell->sp = (cell->sp-1) & (STACK_SIZE-1);
  91 }
  92
  93 void
  94 exec_insn (struct state *state, struct cell *cell)
  95 {
  96   /* Increment cycle counters. */
  97   state->cell_cycle++;
  98   cell->cycle++;
  99
 100   /* State? */
 101   if (cell->state == state_exec)
 102     {
 103       int insn, error;
 104
 105     next:
 106       /* Fetch next insn. */
 107       if (check_exec_access (state, cell, cell->p) ||
 108           chance (access_control_failure))
 109         {
 110           insn = get_soup (state, cell->frag, cell->p);
 111         }
 112       else
 113         {
 114           INC_ERRORS (state, cell);
 115
 116           /* Increment PC */
 117           cell->p++;
 118
 119           return;
 120         }
 121
 122       /* By doing this we allow the cell to use the top two bits of
 123        * each instruction byte for its own purposes. DNA uses a similar
 124        * technique - it can mark up basic sequences by adding its
 125        * own arbitrary chemical markers to each base.
 126        */
 127       insn &= 0x3f;
 128
 129 #if TRACE
 130       trace (cell, insn);
 131 #endif
 132
 133       if (chance (soup_fetch_failure))
 134         {
 135           insn = get_rand_byte () & 0x3f;
 136         }
 137
 138       /* Increment PC */
 139       if (!chance (inc_pc_failure))
 140         {
 141           cell->p++;
 142         }
 143
 144       /* Is this insn going to generate an error? Handle that case
 145        * separately (don't disturb the fast path).
 146        */
 147       error = chance (insn_exec_failure);
 148
 149       if (!error)
 150         {
 151           switch (insn)
 152             {
 153             case 0:             /* NOP0 */
 154             case 1:             /* NOP1 */
 155               return;           /* Ignore. */
 156             case 2:             /* INC A */
 157               cell->a++;
 158               return;
 159             case 3:             /* DEC A */
 160               cell->a--;
 161               return;
 162             case 4:             /* SHL A */
 163               cell->a <<= 1;
 164               return;
 165             case 7:             /* IFZ */
 166               if (cell->a == 0)
 167                 goto next;      /* Fetch and execute next instruction. */
 168               /* Else skip next insn. */
 169               cell->p++;
 170               return;
 171             case 8:             /* FINDB */
 172               if ((cell->plen = get_pattern_length (state, cell)) > 0)
 173                 {
 174                   cell->state = state_find;
 175                   cell->dir = -1;
 176                   cell->i = cell->p - 2;
 177                   cell->lim = FIND_LENGTH_LIMIT;
 178                 }
 179               else
 180                 {
 181                   INC_ERRORS (state, cell);
 182                   cell->i = 0;
 183                 }
 184               return;
 185             case 9:             /* FINDF */
 186               if ((cell->plen = get_pattern_length (state, cell)) > 0)
 187                 {
 188                   cell->state = state_find;
 189                   cell->dir = 1;
 190                   cell->i = cell->p + cell->plen + 1;
 191                   cell->lim = FIND_LENGTH_LIMIT;
 192                 }
 193               else
 194                 {
 195                   INC_ERRORS (state, cell);
 196                   cell->i = 0;
 197                 }
 198               return;
 199             case 0x0a:          /* MALLOC */
 200               if (!cell->daughter &&
 201                   cell->a >= MIN_CELL_SIZE && cell->a <= MAX_CELL_SIZE)
 202                 {
 203                   struct soup_frag *frag
 204                     = soup_frag_malloc (state, cell->frag, cell->a);
 205                   if (frag)
 206                     {
 207                       cell->daughter
 208                         = cell_malloc (state, cell, frag);
 209                       /* Calculate relative address of daughter */
 210                       cell->i
 211                         = cell->daughter->frag->base
 212                         - cell->frag->base;
 213 #if 0
 214                       printf ("MALLOC: dfb = %d, fb = %d, i = %d\n",
 215                               cell->daughter->frag->base,
 216                               cell->frag->base,
 217                               cell->i);
 218 #endif
 219                     }
 220                   else
 221                     {
 222                       /* INC_ERRORS (state, cell); -- Dubious? */
 223                       cell->i = 0;
 224                     }
 225                 }
 226               else
 227                 {
 228                   INC_ERRORS (state, cell);
 229                   cell->i = 0;
 230                 }
 231               return;
 232             case 0x0b:          /* DIVIDE */
 233               if (cell->daughter)
 234                 {
 235                   cell_divide (state, cell, cell->daughter);
 236                   cell_activate (state, cell->daughter);
 237                   cell->daughter = 0;
 238                 }
 239               else
 240                 {
 241                   INC_ERRORS (state, cell);
 242                   cell->i = 0;
 243                 }
 244               return;
 245             case 0x0c:          /* MOVE [I],A */
 246               cell->a = get_soup (state, cell->frag, cell->i);
 247               return;
 248             case 0x0d:          /* MOVE A,[I] */
 249               if (check_access (state, cell, cell->i) ||
 250                   chance (access_control_failure))
 251                 {
 252                   set_soup (state, cell->frag, cell->a, cell->i);
 253                 }
 254               else
 255                 {
 256                   INC_ERRORS (state, cell);
 257                 }
 258               return;
 259             case 0x0e:          /* DMOVE [I],A */
 260               cell->a = get_soup (state, cell->frag, cell->i) << 8;
 261               cell->a |= get_soup (state, cell->frag, cell->i+1);
 262               return;
 263             case 0x0f:          /* DMOVE A,[I] */
 264               if ((check_access (state, cell, cell->i) &&
 265                    check_access (state, cell, cell->i+1)) ||
 266                   chance (access_control_failure))
 267                 {
 268                   set_soup (state, cell->frag, cell->a >> 8, cell->i);
 269                   set_soup (state, cell->frag, cell->a & 0xff, cell->i+1);
 270                 }
 271               else
 272                 {
 273                   INC_ERRORS (state, cell);
 274                 }
 275               return;
 276             case 0x10:          /* XOR A,A (ie. ZERO A) */
 277               cell->a = 0; return;
 278             case 0x11:          /* XOR B,A */
 279               cell->a ^= cell->b; return;
 280             case 0x12:          /* XOR I,A */
 281               cell->a ^= cell->i; return;
 282             case 0x13:          /* XOR P,A */
 283               cell->a ^= cell->p; return;
 284             case 0x14:          /* XOR A,B */
 285               cell->b ^= cell->a; return;
 286             case 0x15:          /* XOR B,B (ie. ZERO B) */
 287               cell->b = 0; return;
 288             case 0x16:          /* XOR I,B */
 289               cell->b ^= cell->i; return;
 290             case 0x17:          /* XOR P,B */
 291               cell->b ^= cell->p; return;
 292             case 0x18:          /* XOR A,I */
 293               cell->i ^= cell->a; return;
 294             case 0x19:          /* XOR B,I */
 295               cell->i ^= cell->b; return;
 296             case 0x1a:          /* XOR I,I (ie. ZERO I) */
 297               cell->i = 0; return;
 298             case 0x1b:          /* XOR P,I */
 299               cell->i ^= cell->p; return;
 300               /* Surely these next three instructions will never be used ... */
 301             case 0x1c:          /* XOR A,P */
 302               cell->p ^= cell->a; return;
 303             case 0x1d:          /* XOR B,P */
 304               cell->p ^= cell->b; return;
 305             case 0x1e:          /* XOR I,P */
 306               cell->p ^= cell->i; return;
 307             case 0x1f:          /* XOR P,P (ie. ZERO P) */
 308               cell->p = 0; return;
 309             case 0x20:          /* PUSH A */
 310               push (cell, cell->a);
 311               return;
 312             case 0x21:          /* PUSH B */
 313               push (cell, cell->b);
 314               return;
 315             case 0x22:          /* PUSH I */
 316               push (cell, cell->i);
 317               return;
 318             case 0x23:          /* PUSH P */
 319               push (cell, cell->p);
 320               return;
 321             case 0x24:          /* POP A */
 322               pop (cell, &cell->a);
 323               return;
 324             case 0x25:          /* POP B */
 325               pop (cell, &cell->b);
 326               return;
 327             case 0x26:          /* POP I */
 328               pop (cell, &cell->i);
 329               return;
 330             case 0x27:          /* POP P */
 331               pop (cell, &cell->p);
 332               return;
 333
 334             default:            /* Unknown instruction. */
 335               INC_ERRORS (state, cell);
 336               return;
 337             }
 338         }
 339       else
 340         {
 341           /* Slow path: insn will execute in error. */
 342           switch (insn)
 343             {
 344             case 2:             /* INC A */
 345               if (chance (2))
 346                 cell->a += 2;
 347               return;
 348             case 3:             /* DEC A */
 349               if (chance (2))
 350                 cell->a -= 2;
 351               return;
 352             case 4:             /* SHL A */
 353               if (chance (2))
 354                 cell->a <<= 2;
 355               return;
 356             case 7:             /* IFZ */
 357               if (chance (2))
 358                 goto next;      /* Fetch and execute next instruction. */
 359               /* Else skip next insn. */
 360               cell->p++;
 361               return;
 362             case 8:             /* FINDB */
 363               if (chance (2))
 364                 cell->i = 0;
 365               return;
 366             case 9:             /* FINDF */
 367               if (chance (2))
 368                 cell->i = 0;
 369               return;
 370             case 0x0c:          /* MOVE [I],A */
 371               cell->a = get_soup (state, cell->frag, cell->i);
 372               if (chance (2))
 373                 cell->a++;
 374               else
 375                 cell->a--;
 376               return;
 377             case 0x0d:          /* MOVE A,[I] */
 378               {
 379                 int i = chance (4);
 380                 switch (i)
 381                   {
 382                   case 0:
 383                     set_soup (state, cell->frag, cell->a+1, cell->i);
 384                     return;
 385                   case 1:
 386                     set_soup (state, cell->frag, cell->a-1, cell->i);
 387                     return;
 388                   case 2:
 389                     set_soup (state, cell->frag, cell->a, cell->i+1);
 390                     return;
 391                   case 3:
 392                     set_soup (state, cell->frag, cell->a, cell->i-1);
 393                     return;
 394                   }
 395                 return;
 396               }
 397             case 0x0e:          /* DMOVE [I],A */
 398               cell->a = get_soup (state, cell->frag, cell->i) << 8;
 399               cell->a |= get_soup (state, cell->frag, cell->i+1);
 400               if (chance (2))
 401                 cell->a++;
 402               else
 403                 cell->a--;
 404               return;
 405             case 0x0f:          /* DMOVE A,[I] */
 406               {
 407                 int i = chance (4);
 408                 switch (i)
 409                   {
 410                   case 0:
 411                     set_soup (state, cell->frag, (cell->a+1) >> 8, cell->i);
 412                     set_soup (state, cell->frag, (cell->a+1) & 0xFF, cell->i+1);
 413                     return;
 414                   case 1:
 415                     set_soup (state, cell->frag, (cell->a-1) >> 8, cell->i);
 416                     set_soup (state, cell->frag, (cell->a-1) & 0xFF, cell->i+1);
 417                     return;
 418                   case 2:
 419                     set_soup (state, cell->frag, cell->a >> 8, cell->i+1);
 420                     set_soup (state, cell->frag, cell->a & 0xFF, cell->i+2);
 421                     return;
 422                   case 3:
 423                     set_soup (state, cell->frag, cell->a >> 8, cell->i-1);
 424                     set_soup (state, cell->frag, cell->a & 0xFF, cell->i);
 425                     return;
 426                   }
 427                 return;
 428               }
 429             case 0x10:          /* XOR ... */
 430               return;
 431             case 0x11:
 432               cell->a = cell->b; return;
 433             case 0x12:
 434               cell->a = cell->i; return;
 435             case 0x13:
 436               cell->a = cell->p; return;
 437             case 0x14:
 438               cell->b = cell->a; return;
 439             case 0x15:
 440               return;
 441             case 0x16:
 442               cell->b = cell->i; return;
 443             case 0x17:
 444               cell->b = cell->p; return;
 445             case 0x18:
 446               cell->i = cell->a; return;
 447             case 0x19:
 448               cell->i = cell->b; return;
 449             case 0x1a:
 450               return;
 451             case 0x1b:
 452               cell->i = cell->p; return;
 453             case 0x1c:
 454               cell->p = cell->a; return;
 455             case 0x1d:
 456               cell->p = cell->b; return;
 457             case 0x1e:
 458               cell->p = cell->i; return;
 459             case 0x1f:
 460               return;
 461             }
 462         }
 463     }
 464   else /* cell->state == state_find */
 465     {
 466       /* During finds,
 467        * cell->p     == address of pattern complement to match
 468        * cell->plen  == length of pattern
 469        * cell->i     == current address of search
 470        * cell->dir   == direction of search (-1 or 1)
 471        * cell->lim   == number of steps before we give up
 472        */
 473       int i;
 474
 475 #if TRACE
 476       trace (cell, -1);
 477 #endif
 478
 479       for (i = 0; i < cell->plen; ++i)
 480         {
 481           int pat = get_soup (state, cell->frag, cell->p+i);
 482           int mat = get_soup (state, cell->frag, cell->i+i);
 483           if (pat > 1 || mat > 1 || pat == mat)
 484             {
 485               /* Not matched: continue searching. */
 486               cell->i += cell->dir;
 487               cell->lim--;
 488               if (cell->lim == 0)
 489                 {
 490                   /* Give up. */
 491                   cell->i = 0;
 492                   INC_ERRORS (state, cell);
 493                   cell->state = state_exec;
 494                   cell->p += cell->plen;
 495                   return;
 496                 }
 497               return;
 498             }
 499         } /* for */
 500
 501       /* Pattern matched! */
 502       cell->p += cell->plen;
 503       cell->state = state_exec;
 504       return;
 505     }
 506 }
 507
 508 #if TRACE
 509 static void
 510 trace (const struct cell *cell, int insn)
 511 {
 512   if (cell->state == state_exec)
 513     {
 514       printf ("x %p A:%d B:%d I:%d P:%d St:[%d %d %d..] e:%d [%p] ",
 515               cell, cell->a, cell->b, cell->i, cell->p,
 516               cell->stack[cell->sp],
 517               cell->stack[(cell->sp-1) & (STACK_SIZE-1)],
 518               cell->stack[(cell->sp-2) & (STACK_SIZE-1)],
 519               cell->errors,
 520               cell->daughter);
 521       switch (insn)
 522         {
 523         case 0: printf ("NOP0"); break;
 524         case 1: printf ("NOP1"); break;
 525         case 2: printf ("INC A"); break;
 526         case 3: printf ("DEC A"); break;
 527         case 4: printf ("SHL A"); break;
 528         case 7: printf ("IFZ"); break;
 529         case 8: printf ("FINDB"); break;
 530         case 9: printf ("FINDF"); break;
 531         case 10: printf ("MALLOC"); break;
 532         case 11: printf ("DIVIDE"); break;
 533         case 12: printf ("MOVE [I],A"); break;
 534         case 13: printf ("MOVE A,[I]"); break;
 535         case 14: printf ("DMOVE [I],A"); break;
 536         case 15: printf ("DMOVE A,[I]"); break;
 537         case 16: case 17: case 18: case 19:
 538         case 20: case 21: case 22: case 23:
 539         case 24: case 25: case 26: case 27:
 540         case 28: case 29: case 30: case 31:
 541           printf ("XOR %c,%c", "ABIP"[insn&3], "ABIP"[(insn>>2)&3]); break;
 542         case 32: case 33: case 34: case 35:
 543           printf ("PUSH %c", "ABIP"[insn&3]); break;
 544         case 36: case 37: case 38: case 39:
 545           printf ("POP %c", "ABIP"[insn&3]); break;
 546         default: printf ("unknown %d", insn); break;
 547         }
 548       printf ("\n");
 549     }
 550   else
 551     {
 552       printf ("f %p I:%d P:%d dir:%d plen:%d lim:%d\n",
 553               cell, cell->i, cell->p, cell->dir, cell->plen, cell->lim);
 554     }
 555 }
 556 #endif