## Saturday, 22 June 2013

### A bubble sort function

A bubble sort is the simplest sorting algorithm. It compares each vector element with it's successor and swaps them if they are out of order. It is inefficient, but sufficient for small vectors.

```# this subroutine bubble sorts vectors of words
#
# inputs
#   r0 - start of vector
#   r1 - number of elements to sort
#
# no outputs
#
# locals
#   r4 - current pointer
#   r5 - inner counter
#   r6 - keep_going flag
#   r7 - first element
#   r8 - second element

.equ datum_size,4                                   @ works with 4 byte (32 bit) words
.globl _bubble
.text
_bubble:
stmfd sp!, {r4, r5, r6, r7, r8, lr}                @ save variables to stack
cmp r1, #1                                         @ number of elements must be > 1
ble end_outer                                      @ stop if nothing to do

sub r5, r1, #1                                     @ need n-1 comparisons
mov r4, r0                                         @ initialise current pointer
mov r6, #0                                         @ this register set when we swap

loop_start:
ldr r7, [r4], #datum_size                          @ load one element
ldr r8, [r4]                                       @ and next one
cmp r7, r8                                         @ compare them
ble no_swap                                        @ branch if second greater

mov r6, #1                                         @ set keep_going flag
sub r4, r4, #datum_size                            @ reset pointer to first element
swp r8, r8, [r4]                                   @ exchange value in r8 and address in r4
str r8, [r4, #datum_size]!                         @ store new r8 to incremented address
no_swap:
subs r5, r5, #1                                    @ decrement counter
bne loop_start                                     @ and restart loop if more needed

end_inner:
cmp r6, #0                                         @ check keep_going flag
beq end_outer                                      @ and leave if not set

mov r6, #0                                         @ clear keep_going flag
mov r4, r0                                         @ reset pointer
sub r5, r1, #1                                     @ reset counter
b loop_start                                       @ start another iteration

end_outer:
ldmfd   sp!, {r4, r5, r6, r7, r8, pc}       @ restore state from stack and leave subroutime

```

A bubble sort test harness to use the subroutine

```@ An example of moving data from memory to a register
.globl main
.equ items,16                       @ maybe would use evalues - values >> 2 if it weren't a demo?
.section .rodata
before:
.asciz "Before sorting, values are : %d"
after:
.asciz "After sorting,  values are : %d"
comma:
.asciz ", %d"
new_line:
.asciz "\n"
ok:
.asciz "ok\n"
.section .data
values:
.word 105, -7, 235, 61, 28, 315, 456, 63, 134, 97, 221, 53, 1000899, 145, 117, 5
evalues:
.text
main:
ldr r0, =values                    @ the start of the vector
mov r1, #items                     @ how many elements to print
ldr r2, =before                    @ the start string
ldr r3, =comma                     @ string for subsequent elements
bl _vprintw                        @ print the unsorted vector
ldr r0, =new_line
bl  printf                         @ print the newline

ldr r0, =values                    @ the start of the vector
mov r1, #items                     @ how many elements to sort
bl _bubble                         @ call the sort routine

ldr r0, =values
mov r1, #items
ldr r2, =after
ldr r3, =comma
bl _vprintw                        @ print the sorted vector
ldr r0, =new_line
bl  printf

mov     r7, #1                     @ set r7 to 1 - the syscall for exit
swi     0                          @ then invoke the syscall from linux
```
```bob@poland:~/www/examples\$ make bubble
/usr/bin/gcc -gstabs -o bubble bubble.s bubble_sub.s vprintw.s
bob@poland:~/www/examples\$ ./bubble
Before sorting, values are : 105, -7, 235, 61, 28, 315, 456, 63, 134, 97, 221, 53, 1000899, 145, 117, 5
After sorting,  values are : -7, 5, 28, 53, 61, 63, 97, 105, 117, 134, 145, 221, 235, 315, 456, 1000899
bob@poland:~/www/examples\$
```

1. Gives segmentation fault

1. ;Try this one

AREA Example8Point5, CODE
ENTRY

EXPORT Main
SRAM_BASE EQU 0x20000000
number EQU 25

ENTRY ; mark first instruction

Main

MOV r10,number
LDR r1,[r0]
LDR r9,=SRAM_BASE

LDR r2,[r0],#4
STRB r2,[r9],#1
SUBS r10,#1
CMP r10,#0

MOV r11,number ;outer Loop
MOV r8,number ;Inner Loop
MOV r7,0

FirstLoop
LDR r9,=SRAM_BASE
SUB r10,r8,r7
CMP r11,#0
BNE SecondLoop
BEQ Exit
SecondLoop

CMP r10,#0
SUB r11,1
; BMI FirstLoop
BEQ FirstLoop
LDRB r1,[r9]
LDRB r2,[r9,#1]
SUB r10,r10,#1
CMP r1,r2
BGT SWAP
BLE Decrease_r9
B SecondLoop

Decrease_r9
B SecondLoop

SWAP
STRB r2,[r9]
STRB r1,[r9,#1]
B SecondLoop

MOV r8,#4

;Values DCD 8,6,3,5,2,7,5,2,4,3,22,45,12

Values DCD 7, 5, 2, 4, 3, 9,2,3,4,5,8,10,22,45,12,7,7,7,0,1,0,0,0,0,1 ;number=25

;Values DCD 7, 5, 3, 4, 3, 3,2,3 ;number=8
; 0x16 0x2D 0xC
;0x2D 0x38 0x18 0x4E 0x41

Exit
END