ECE243

Spring 2005

Andreas Moshovos

Subroutines – Examples

We will look at two subroutine examples. We may not cover both of them during the lectures. You may use those that we do not cover as practice questions. That is, try to develop code for the C equivalents and then compare your solution to the ones presented here.

1. Searching Through a Sorted Binary Tree

A binary tree is a data structure comprising several nodes. Each node has three components:

1. A data value

2. A left child

3. A right child

Both children are also nodes. In C we can define a tree using the following structure:

struct node_t

{

int value;

struct node_t *left;

struct node_t *right;

}

A binary tree is sorted if the following two conditions apply at each node:

1. The values of all nodes in the left subtree of a node are less than the value of the node.

2. The values of all nodes in the right subtree of a node are greater than or equal to the value of the node.

The following figure shows a sorted binary tree:

The following C function searches a sorted binary tree for a given value. It returns 1 if the value is found otherwise it returns 0:

int

search_st (struct node_t *tree, int value)

{

struct node_t *curr = tree;

while (curr)

{

if (curr->value == value) return 1; // value found

if (value < curr->value) // if value less than that of the current node search the left

curr = curr->left; // subtree

else curr = curr->right; // search the right subtree

}

return 0;

}

This routine uses the curr pointer to start searching from the top node following the left or right child pointers until either the value is found or there are no more nodes to search. The following figure shows the path the function will follow if called to search for value 13.

At the machine level the tree has to be represented in memory. Each node can be represented using three consecutive long words in memory. The first can be used to hold the data value, the second longword contains a pointer to the left child while the third longword contains a pointer to the right child. A pointer has a value which can be used as an address to refer to some other object in memory. Here’s a series of “DC” assembler directives that form our example tree:

NULL equ 0

org $30000

node0 dc.l 10, node1, node2 ; top node

node1 dc.l 5, NULL, node3 ; top node’s left child

node2 dc.l 20, node4, node5 ; top node’s right child

node3 dc.l 8, NULL, NULL

node4 dc.l 15, NULL, NULL

node5 dc.l 30, NULL, NULL

Note that the exact order in which the nodes appear in memory is *not* important. That is the following statements define the same tree (when viewed in the abstract) but with a different in memory layout:

NULL equ 0

org $30000

node2 dc.l 20, node4, node5 ; top node’s right child

node0 dc.l 10, node1, node2 ; top node

node3 dc.l 8, NULL, NULL

node1 dc.l 5, NULL, node3 ; top node’s left child

node5 dc.l 30, NULL, NULL

node4 dc.l 15, NULL, NULL

The next important step is to figure out what the stack layout should be for a correct implementation of st_search. This subroutine takes two arguments: a pointer and a value. So, the stack when st_search is called should contain three long words as follows:

A7à	Return address
	Parameter tree
	Parameter value

With this in hand now we can start writing the subroutine. A concern any time we start developing a subroutine is that often we cannot tell immediately how many registers and local variables (allocated on the stack) we will need. This is important to know as we will have to save registers on the stack prior to using them and since we will have to allocate local variables on the stack. The net effect will be that the relative distance from the stack pointer of the parameters may change. A methodology that would work is to write the subroutine using names for the various parameters and locals and once the subroutine is complete to rewrite saving/restoring any registers we used and replacing parameter names with appropriate displacements from the top of the stack:

Here’s the first implementation that uses names for parameters and ignores saving/restoring registers:

search_st

move.l value, d0 ; d0 holds the value we are searching for

movea.l tree, a0 ; we use a0 for curr. This does curr = tree

loop cmp.l #0, a0

beq notfound ; if curr == 0 then exit the while loop

move.l (a0), d1 ; read curr->value into d1

cmp.l d1, d0 ; compare curr->value and value

beq found ; (curr->value == value)

bgt goleft ; (curr->value < value)

goright movea.l 8(a0), a0 ; curr = curr->right

; note that 0(a0) = value

; 4(a0) = left

; 8(a0) = right

bra loop

goleft movea.l 4(a0), a0 ; curr = curr->left

bra loop

found move.l #1, d0 ; found, return value = 1

bra epilogue

notfound clr.l d0 ; not found, return value = 0

epilogue

rts

As we can now see we used registers a0, d0 and d1. We do not need to save d0 since we can changed it freely as it used for the return value. We should save a0 and d1 (in GNU’s gcc I think that a0 is used for the return value when a subroutine returns a pointer C datatype). Thus after the prologue section of search_st the stack will look as follows:

A7à	Saved a0	+0
	Saved d1	+4
	Return address	+8
	Parameter tree	+12
	Parameter value	+16

Now that we have figured out what we need to put on the stack we can rewrite the function (changes/additions shown in bold):

search_st

movem.l d1/a0, -(a7) ; save the registers we change

move.l 16(a7), d0 ; d0 holds the value we are searching for

movea.l 12(a7), a0 ; we use a0 for curr. This does curr = tree

loop cmp.l #0, a0

beq notfound ; if curr == 0 then exit the while loop

move.l (a0), d1 ; read curr->value into d1

cmp.l d1, d0 ; compare curr->value and value

beq found ; (curr->value == value)

bgt goleft ; (curr->value < value)

goright movea.l 8(a0), a0 ; curr = curr->right

; note that 0(a0) = value

; 4(a0) = left

; 8(a0) = right

bra loop

goleft movea.l 4(a0), a0 ; curr = curr->left

bra loop

found move.l #1, d0 ; found, return value = 1

bra epilogue

notfound clr.l d0 ; not found, return value = 0

epilogue

movem.l (a7)+, d1/a0 ; restore the registers we changed to their original values

rts

SECOND EXAMPLE: Detecting whether a string is a palindrome (or carcinic)

A series of letters is a palindrome if it reads exactly the same if read from left to right or from right to left. For example “abba” is a palindrome and so is “lalal”. “lala” is not a palindrome.

We want to write a function that returns 1 if its string parameter is a palindrome. The function should return a 0 otherwise. Before we do so, let’s first explain what is a string. A string at the machine level is a sequence of bytes. The C implementation of strings uses a zero-terminated sequence of bytes. That is, the end of the string is marked by a byte whose value is zero. This zero is not part of the string, it only marks its end. Hence we cannot have a string that contains the 0 byte. So, “abba” will be represented as five bytes with values: ‘a’, ‘b’, ‘b’, ‘a’ and 0, where for example ‘a’ is the ASCII code for the character a. So, if in C we write:

char s[] = “abba”;

In assembly we would write:

s dc.b ‘a’, ‘b’, ‘b’, ‘a’, 0

So, a string is really an unidimensional array. So, using just “s” we are effectively referring to the address of its first element (same as &s[0]).

The function palindrome will have the following interface:

int

palindrome (char *a)

{

}

Hence “a” will be a long word whose value is the address where the string starts at.

Here’s an implementation of palindrome in C:

int

palindrome (char *a)

{

char *e;

if (a == NULL) return 1; // NULL string is a palindrome (we define this)

e = a;

while (*e != 0) e++; // find the terminating zero

if (e == a) return 1; // empty string (just a terminating zero) is a palindrome

e--; // point to the last character

while ((*a != 0) && (*a == *e))

{

a++;

e--;

}

if (*a == 0) return 1; // is a palindrome

return 0;

}

Here’s the implementation where we initially ignore saving/restoring registers and the actual distance of parameters from the top of the stack:

org $20000

palindrome

movea.l a, a0 ; get the string’s starting address into a0

beq isP ; if NULL return 1

movea.l a0, a1 ; e lives in a1, copy a into a1

loop1

move.b (a1), d1 ; read *e into d1

beq loop1Done ; if (*e == 0) done

addq.l #1, a1 ; e++

bra loop1

loop1Done

cmpa.l a1, a0 ; if (e == a) return 1

beq isP

subq.l #1, a1 ; e—

loop2

move.b (a0), d0 ; d0 = *a

beq loop2Done

move.b (a1), d1 ; d1 = *e

cmp.b d1, d0 ; if (*a != *e) done

bne loop2Done

addq.l #1, a0

subq.l #1, a1

bra loop2

loop2Done

cmp.b #0,d0 ; if (*a == 0) return 1

beq isP

isnotP

clr.l d0

bra epilogue

isP

move.l #1, d0

epilogue

rts

So, we are changing registers d0, d1, a0 and a1 and thus we need to save the last three. Here’s the updated code:

org $20000

palindrome

movem.l d1/a0-a1, -(a7)

movea.l 16(a7), a0 ; get the string’s starting address into a0

beq isP ; if NULL return 1

movea.l a0, a1 ; e lives in a1, copy a into a1

loop1

move.b (a1), d1 ; read *e into d1

beq loop1Done ; if (*e == 0) done

addq.l #1, a1 ; e++

bra loop1

loop1Done

cmpa.l a1, a0 ; if (e == a) return 1

beq isP

subq.l #1, a1 ; e—-

loop2

move.b (a0), d0 ; d0 = *a

beq loop2Done

move.b (a1), d1 ; d1 = *e

cmp.b d1, d0 ; if (*a != *e) done

bne loop2Done

addq.l #1, a0

subq.l #1, a1

bra loop2

cmp.b #0,d0 ; if (*a == 0) return 1

beq isP

isnotP

clr.l d0

bra epilogue

isP

move.l #1, d0

epilogue

movem.l (a7)+, d1/a0-a1

rts

There are ways of optimizing the routine at the algorithmic level. Our goal here was to illustrate one possible implementation.