Tutorials - SIC/XE stack
Tutorials - SIC/XE stack
Stack - first try
- Have you noticed that SIC/XE computer does not directly support stack?
- Why we need stack?
- Where is stored the return address when we use the instructions JSUB and RSUB?
- How would you implement a recursive subroutine in SIC/XE assembly?
- How high-level programming languages compile function calls? How are the parameters transferred?
Some assembly languages support stack with a special PUSH/POP instructions for push a register to the stack and popping a value from the stack to a register. Thus, in SIC/XE, we may need routines such as:
- PUSHA, POPA, PUSHS, POPS, PUSHT, POPT, PUSHL, POPL
Think about this proposal:
- How would you implement these routines?
- What is the difference between PUSHA and PUSHL?
- What is the problem with PUSHL?
- Do we really need PUSHL and POPL? If yes then when, where?
Stack - second try
Implementation of all routines from the previous exercises is quite repetitive and boring and we may actually not need all of them. So let us simplify a bit.
We perform a push to the stack in two steps: first, we copy a specific register to the stack, second we change (increment) stack pointer. Similarly, we perform a pop operation: first, we decrement the stack pointer and then we copy the value from the stack to the specific register.
- A stack ponter stackptr pointing to the first free word (just above the top) of the stack.
- Two routines called stackpush, stackpop for incrementing and decrementing the stack pointer.
- We will actually manually copy the registers to the stack or from it.
Example of push operation, e.g. pushing the register A to the stack:
STA @stackptr . store A to the top of stack
JSUB stackpush . increment the stack pointer
Example of pop operation, e.g., popping the register A from the stack:
JSUB stackpop . decrement the stack pointer
LDA @stackptr . copy the top of stack to the register
Now, your task is only to implement the following three subroutines:
- stackinit - stack initalization (initialize stackptr, reserve a predefined memory area)
- stackpush - increment the stack poitner
- stackpop - decrement the stack pointer.
Using the stack subroutines from the above exercise write a subroutine for recursive calculation of the factorial function, i.e., n!, where the number n is transferred via register A and the result is put into the register A as well.
Use the subroutines for input/output to print several factorials.
* Hanoi towers
Everybody knows Hanoi towers puzzle - Wikipedia.
Write a subroutine for solving this puzzle, where the solution is the sequence of moves which are needed to move all the disks from tower A to C. For example, move A>B means to move one disk from A to C.
- Store the number of disks in the register A.
- Store the labels of disks in the register S - for each tower one byte (character code). For example, ACB in the register represents configuration: moving from A to C through B.
Input: the number of disks n, labels of 1., 2., 3. tower (start, end, intermediate).
- Transfer n-1 disks from 1. to 3. (via 2.)
- Move one disk from 1. to 2.
- Transfer n-1 disks from 3. to 2 (via 1.)