## 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.

We need:

- 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.

## Factorial

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.

Hints:

- 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).

Algorithm:

- 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.)