Computer Science 237
Computer Organization

Williams College
Fall 2005

Lab 7: Langton's Ant
Due: Monday, October 31, 2005 at 11:00 AM

No formal lab meeting this week!

This week, your task is to translate the C-based ant-movement method in a simulator for Langton's Ant that runs on the Palm. This method is called JDTMoveAnt in the file ant.c. You should write an assembly method MoveAnt in the file MoveAnt.s, and turn in only that file.

Here are the specific steps:

  1. Untar the starter kit:
        tar xvfz /usr/cs-local/share/cs237/labs/ant/ant.tar.gz

    This creates a subdirectory, ant, that contains all of the usual files, including ant.c and MoveAnt.s

  2. If you type make it will make a working version of the program. You should run the program and make sure you know how it works. Your method will be invoked one or more times by pressing the go button. The README file in the ant directory explains the other buttons. You can change some of the configuration details near the top of ant.c. It is best not to make any changes until you have a fully functioning program.
  3. Carefully translate the routine JDTMoveAnt into an assembly language routine, MoveAnt. Your source should be stored in the file MoveAnt.s. The only symbol that you must make .globl is MoveAnt.
  4. When you believe you have a working version of your assembly language code, you should modify the line
       void (*MOVEANT)(int*,int*,int*,UInt8[],int) = JDTMoveAnt;
    to read
       void (*MOVEANT)(int*,int*,int*,UInt8[],int) = MoveAnt;

    This declares a pointer to a function, initialized to point to JDTMoveAnt. When you change the pointer value, any calls to MOVEANT become calls to your code. You might find the call to MOVEANT--it looks pretty much like any other call. That's because a function is normally represented by a pointer to its first instruction.

  5. Run your code. You should be able to single step the ant and verify its behavior.
  6. When you are satisfied with your solution, turn it in:
        turnin -c 237 MoveAnt.s

Here's the code you are to convert, found at the top of the ant.c file:

extern void JDTMoveAnt(int*,int*,int*,UInt8[],int);
extern void MoveAnt(int*,int*,int*,UInt8[],int);

/* Change the following assignment to be ... = MoveAnt to use your code */
void (*MOVEANT)(int*,int*,int*,UInt8[],int) = JDTMoveAnt;
/* Ant is located at (Antx,Anty), pointing in direction AntDir, where
 * 0 => North, 1 => East, 2 => South, 3 => West
 * world is the toroidal array of bits.  Bits (0,0) through (0,7) are stored
 *    in world[0]; bits (0,8) through (0,15) are stored in world[1], etc.
 *    This is a packed "row-major ordering."
 * size is the width of each row of this logical 2D array, in bits
 * WARNING: size may be a value other than a power of 2.
void JDTMoveAnt(int *Antx, int *Anty, int *AntDir, UInt8 world[], int size)
    int i;
    int x = *Antx, y = *Anty, d = *AntDir;
    i = x+y*size;
    if (world[i/8]&(1<<(i%8))) {
        d = (d+1)%4;
    } else {
        d = (d+3)%4;
    world[i/8] ^= (1<<(i%8));
    if (d & 1)
        x = (x+size-d+2)%size;
    } else {
        y = (y+size+d-1)%size;
    *Antx = x;
    *Anty = y;
    *AntDir = d;