Project 6: Stack architectures

Project 6
Objectives:
~~~~~~~~~~~

- Sharpen you C programming skills
- Learn about stack architectures

Assignment:
~~~~~~~~~~~

Finish the implementation of a simulator for a stack machine

Stack architecture:
~~~~~~~~~~~~~~~~~~~

Is a computer architecture in which most operands are stored on an implicit
stack rather than in general purpose registers or memory.

Hardware implementations of stack architectures are rare but a number of
virtual machines (e.g. the standard Java runtime) define stack machines
interpreted in software.

Our machine state:
~~~~~~~~~~~~~~~~~~

- 32 bit words
- Machine state
* A 1024 word stack
* A 1024 word data memory (word addressable)
* A 1024 character program memory. Each instruction is a single ASCII
character
* A stack pointer
* A program counter initialized to 0
- The machine halts when the PC is set to -1

The instruction set:
~~~~~~~~~~~~~~~~~~~~

'.' return from function -- PC = pop()
'-' subtract -- push(pop() - pop())
'+' add -- push(pop() + pop())
'*' multiply -- push(pop() * pop())
'/' divide -- push(pop() / pop())
'%' mod -- push(pop() % pop())
'<' branch if negative -- t = pop(); val = pop() ; if (val < 0) PC = t
'' branch if positive -- t = pop(); val = pop() ; if (val 0) PC = t
'=' branch if equal -- t = pop(); val = pop() ; if (val == 0) PC = t
'e' branch if empty -- t = pop(); if (stackIsEmpty) PC = t
'c' call -- t = pop(); push(PC+1); PC = t
'd' duplicate the top element -- t = pop(); push(t); push(t)
'l' load from memory -- a = pop(); push(mem[a])
'p' pop -- pop()
's' store to memory -- a = pop(); v = pop(); mem[a] = v
'x' exchange the top two stack elements

'0'..'9' a sequence of decimal digits is interpreted as a decimal integer
and pushed on the stack

The simulator API (defined in sim.h)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

- struct StateStruct is an opaque struct that defines the machine state. The
actual implementation should be defined in sim.c

- State is a convenient typedef for "struct StateStruct"

- State* init(); // create a new machine state, PC = 0, empty stack, ...

- void prog(State* s, char* p); // set the program

- void push(State* s, int value); // push the given value on the stack

- void run(State* s); // run the machine until PC == -1

- void stack(State* s); // dump the contents of the stack as a decimal
// ints (one per line)

Files:
~~~~~~

Do not change:

main.c : the main program
sim.h : the simulator header file
Makefile : the Makefile
neg.ok, max.ok, fact.ok : expected output from tests

Change:

sim.c : The simulator implementation

Generated by Makefile:

neg.out, max.out, fact.out : output from running the test cases


To Compile:
~~~~~~~~~~~

make

To Run:
~~~~~~~

make run

To Test:
~~~~~~~~

make test

Expected output from make test
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

....
neg : PASS
max : PASS
fact : PASS