Big Example of Assembly Program

This example teaches you to "integrate" your knowledge about machine instructions that you know so far.  We will show a "non-trivial" high level language that do some useful work, then show you how to write an assembly language program for Z0 processor step-by-step.

Goal

Write a function that check whether an integer x is in a list, L. Given L as a linked list with this structure.

A list consists of a chain of cells.  A cell is a two-adjacent-word (each 32 bits) object.  The first word of a cell is called "head".  The head contains the information (in our case, an integer).  The next word of a cell is called "tail".  The tail contains the "pointer" (index, or an address) of the chain to the next cell. The last cell of a list is terminated by 0. A list is depicted below: a list of (3,10,7)

---------       ---------           ---------
| 3 |   | ----> | 10|   | ----> ... | 7 | 0 |
---------       ---------           ---------
head  tail

Here is the program to test the membership of x to a list L.

member(x, L)
  while L != 0 
    if head(L) == x  return YES
    L = tail(L)
  return NO

We need to overcome two "complex" functions: head, tail.  The "head" gets the information directly from the cell L.  The "tail" gets the link (or address) from the next cell of L.  Here is the Z0 instruction to do it. Let L be stored in r3.  That is r3 contains the pointer (address) to the list L.

head(L)    is   ldd r3              ; R[0] = M[R[3]], load indirect
tail(L)    is   inc r3, ldd r3      ; R[0] = M[R[3]+1]

The first thing we do before we start to write machine code is assigning registers to variables that we need.

Let x be r1, L be r3.
Let L be 200, resides in the data memory
Return value in r0, 1 - yes, 0 - no

Code

:member
  mvi x
  put r1      r1 = x
  mvi 200    
  put r3      r3 = L
:while
  z r3        ; L == 0?
  jt exit
  ldd r3
  eq r1       ; head(L) == x?
  jt Yes
  inc r3
  ldd r3
  put r3       ; L = tail(L)
  jmp while
:Yes
  mvi 1
  stop
:No
  mvi 0
  stop

Exercise

Code the above program into machine codes and run it using the Z0 simulator.  You must put the list L into data memory first.
Here is how:  the first cell of L is at 200.  The list is (3,10,7). Note: the pair-cells in the real list may not be consecutive as in this example because each pair-cell may be allocated in a different address.

address  data

200     3
201     202
202     10
203     204
204     7
205     0

last update 3 Sept 2014