ECAD & Architecture Workshop Five

Sorting using ARM assembler

workshop home | workshops: 1 | 2 | 3 | 4 | 5 | 6

Task

The task is to write a program which reads in a list of strings, sorts them and prints them out.

Allocate one pool of space to store the strings using "%" operator (refer to last workshop). Strings should not be allocated a fixed amount of space per string, rather pack the strings into the large allocated space so that the space is used efficiently. It is probably easiest to store the strings as an array of characters terminated by null (ASCII code 0, written '\0' in assembler).

A table of pointers to the strings should also be built. During sorting, swapping strings over just requires the appropriate pointers in this table to be swapped.

The code to perform the sort should be a subroutine which accepts a pointer to the table of string references. The sort routine should call another routine to actually compare a pair of strings. The comparison of strings should be done on ASCII character values with the first character being the most significant.

The strings should be read in one per line ('\n' is the end of line character). The end of input should be indicated by entering a line with a single full stop ('.') on it.

The characters can be read from the keyboard one at a time using the appropriate SWI call. The debugger ROM on the board defines a number of useful SWIs, all of which are accessed by putting the function code in r0 and executing a SWI 0x123456 instruction. Note that reading a character will not result in a character being displayed on the console window, so you have to echo the character yourself (so the user gets some feedback).

Function	Code in r0	Arguments in r1	Returns
SYS_WRITEC	0x3	A pointer to a character to be printed.	None
SYS_WRITE0	0x4	A pointer to a null-terminated string to be printed.	None
SYS_READC	0x07	Must be zero.	A character read from the debugger's input window.
Angel_ReportException	0x18	An exception code; the most useful one is 0x20026 (exit)	Does not return.

E.g., to read a character:

	mov	r0,#7
	mov	r1,#0
	swi	0x123456

These routines may corrupt the values of r4-r12, and r14, so you should save them before calling if you are using them (see last workshop for examples). The character typed will be returned in r0.

Hint: build up this program slowly, starting with a program which reads and writes a single string, then multiple strings without sorting, and finally with sorting.

Remember to comment your code.

Question

How many comparison subroutine calls will be made to sort the following strings, in the given order:
```
elude
marmalade
elephant
arm
wombat
grapefruit
elephants
elude
ARM
```

Ticking Criteria

Your code needs to be cleanly formatted and commented.
You must make good use of procedure calls to reduce the complexity of any one code segment (this is for your sanity as well as the demonstrator's!). In particular, your string comparison routine must obey ARM procedure calling standards (pointers to strings passed in registers r0 and r1, the result returned in r0; r2-r3,r12 do not need to be preserved but other registers do if the are used - see page 11 of the Computer Design notes).
You must give a live demonstration of your solution.
Answers to the questions for the lab must be added to the end of your code.

The following header must be added to all code submitted:

;;----------------------------------------------------------------------
;; ECAD+Arch Workshop 5
;; Your name
;; Your college
;; date
;;----------------------------------------------------------------------