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$

3 comments:

  1. Replies
    1. ;Try this one

      AREA Example8Point5, CODE
      ENTRY

      EXPORT Main
      SRAM_BASE EQU 0x20000000
      number EQU 25

      ENTRY ; mark first instruction

      Main

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

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


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

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

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

      Decrease_r9
      ADD r9,r9,#1
      B SecondLoop

      SWAP
      STRB r2,[r9]
      STRB r1,[r9,#1]
      ADD r9,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

      Delete
  2. Hey hello, can you share CPUlator version of this code if you have? Thanks

    ReplyDelete