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.)
Last modified: Tuesday, 23 October 2018, 10:53 PM