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
