ARM project: Week 2
String sort in ARM assembler


ARM project home | Tasks (weeks): 1 | 2 | 3 | 4

ARM Developer Suite

            ; Hello world in ARM assembler

            AREA text, CODE
            ; This section is called "text", and contains code

            ENTRY

            ; Print "Hello world"

            ; Get the offset to the string in r4.
            adr       r4, hello           ;; "address in register"

loop        ; "loop" is a label and designates an address
            ; Call putchar to display each character
            ; to illustrate how a loop works

            ldrb      r0, [r4], #1        ; Get next byte and post-index r4
            cmp       r0, #0              ; Stop when we hit a null
            beq       outputstring        ;; "branch if equal" = cond. goto

            bl        putchar             
            b         loop                ;; "branch" =  goto

outputstring
            ; Alternatively, use putstring to write out the
            ; whole string in one go
            adr       r0, hello
            bl        putstring           ;; "branch+link" = subroutine call

finish
            ; Standard exit code: SWI 0x123456, calling routine 0x18
            ; with argument 0x20026
            mov       r0, #0x18
            mov       r1, #0x20000        ; build the "difficult" number...
            add       r1, r1, #0x26       ; ...in two steps
            SWI       0x123456            ;; "software interrupt" = sys call

hello
            DCB       "Hello World\n",0

            END

You may need to reformat the code a little. In particular, labels may not be preceded by any white space.

; I/O routines

            AREA      text,CODE
                                                
            EXPORT    printhex, putchar, putstring

printhex
            ; Print number in r0 as 8 hex digits
            ; Conforms to APCS
            stmfd     sp!, {r4, lr}

            adr       r2, hex_digits
            adr	      r3, print_hex_string
            mov       r4, #28

printhex_loop
            ;; For r4 = 28 to 0 step -4
            mov       r1, r0, lsr r4	; Get digit n
            and       r1, r1, #0x0f	; mask off lower nibble
            ldrb      r1, [r2, r1]	; r0 now contains a hex number, 
                                    ;look it up in table
            strb      r1, [r3], #1
            subs      r4, r4, #4
            bpl       printhex_loop

            adr       r0, print_hex_string
            bl        putstring

            ldmfd     sp!, {r4, pc}

hex_digits
            DCB       "0123456789ABCDEF"
print_hex_string
            DCB       "12345678",0	; storage for 8 digit hex string, 
                                    ; null terminated
            ALIGN


putchar
            ; Entry: Takes char in r0.
            ; Conforms to APCS
            ; Call SYS_WRITEC, with r1 containing a POINTER TO a character.

            ; SYS_WRITEC = 3, SYS_WRITE0 = 4, SYS_READC = 7

            stmfd     sp!, {r4-r12, lr} ; push the registers that 
                                        ; you want to save

            adr       r1, putchar_temp
            strb      r0, [r1]
            mov       r0, #3
            swi       0x123456

            ldmfd     sp!, {r4-r12, pc} ; and pop them once you're back

putchar_temp
            DCB       0

            ALIGN

putstring
            ; Entry: Takes pointer to a null terminated string in r0
            ; Conforms to APCS
            ; uses Call SYS_WRITE0

            stmfd     r13!, {r4-r12, lr}

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

            ldmfd     r13!, {r4-r12, pc}

            END
            IMPORT    printhex
            IMPORT    putchar
            IMPORT    putstring

AXD (ARM Debugger for Windows and UNIX)

Start AXD with Project | Debug.

When AXD loads, it may ask you to choose a target. This refers to running the program on the ARM board, rather than in the emulator. As the link to the board is rather slow, we'll run the first half of this exercise in the emulator (select ARMUL).

Now, let's go back and look at the program's execution in more detail.

In summary, "step in" (F8) will do one instruction at a time; "step over" will do one instruction or subroutine at a time; and breakpoints halt the run whenever they are hit. They provide different granularities of control over debugging.

Now try it on the ARM board. To do this:

  1. Make sure the board is connected to your PC via a serial cable (not the Altera's parallel cable) and switched on.
  2. Select Options | Configure Target..., and click on ADP.
  3. Configure it like this:

Once you get all this prewritten code going, flex your muscles by adding some code of your own to "hello.s" so that it also writes out "2+2=", computes the result in assembler, and prints the result (as a 32-bit hex number) by calling printhex.

Task

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

Allocate a pool of space to store the strings using the "%" operator. This is done by adding the following just before the END line:

            ALIGN     4  ; ensure allocated memory is word aligned
strings     %         4096

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 use the conventions of C and 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). Don't worry about providing editing facilities such as backspace or cursor movement.

Function Code in r0 Arguments in r1 Returns
SYS_WRITEC0x3 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 ioroutines.s 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 1

W2-Q1: How many comparison subroutine calls will be made to sort the following input?

elude
marmalade
elephant
arm
wombat
grapefruit
elephants
elude
ARM

Question 2

W2-Q2: If you were given the job of testing your neighbour's program, with a prize for every crash you could provoke, what kind of "poisoned" inputs would you feed it?

(Note: do not take this to imply that you will lose marks unless you make your own program absolutely bulletproof. For the limited purposes of this week's workshop, if it works on "regular" inputs, it's ok. However, as a designer, you must be aware of the pitfalls of writing low level code, which this week's experience may have highlighted.)

Weekly mini-report

Submit the following to one of the demonstrators before the end of the last session of this week on Thursday morning.

  1. The ARM code for the string sort (but not any supplied code) needs to be cleanly formatted and commented. Don't submit the hello and 2+2 code.
  2. You must make good use of procedure calls to reduce the complexity of any one code segment (this is for your own sanity as well as the demonstrator's!). In particular, your string comparison routine should obey ARM procedure calling standards (arguments passed in registers r0-r3, result returned in r0; registers r4-r11 and r13 cannot be corrupted by the subroutine and must be preserved if they are used; more details on page 11---actually page 13 in the PDF file---of the Computer Design notes).
  3. You must give a live demonstration of your solution.
  4. Answers to the two questions for this week must be added to the end of your code.
  5. The following header must be added to all code submitted:
    ;//////////////////////////////////////////////////////////////////////////////
    ;// ARM Project - Week 2
    ;//
    ;// Your name
    ;// Your college
    ;// date
    ;//////////////////////////////////////////////////////////////////////////////
    
  6. Complete one of the supplied cover sheets and prepend it to the listing.
Please don't leave this to the last moment: expect queues for the demonstrators' attention during the last hour, and remember that the laboratory is booked by another course from 13:00 onwards. The penalty for not submitting by Thursday is 3 marks per weekday.