ARM Assembler Regular Bubble Sort

0
votes

I tried to write a simple bubblesort in ARM Assembler on a basis of a given C bubblesort code:

bubbleSort (int A[], int n)
{
    int temp;
    int i;
    do {
        swapped = false;
        n = n-1;
        for (i=0; i < n; i++) {
            if ( A[i] > A[i+1] ) {
                temp = A[i];
                A[i] = A[i+1];
                A[i+1] = temp;
                swapped = true;
            }
        }
   } while (swapped == true);
}

And here is my assembler code I wrote so far:

bubblesort:
      @ maybe r0, r1 for table and counter (rest is based on that)
      @ r8 = Buffer for Value
      @ r4 = Counter for loop1
      @ r5 = Register for Value
      @ r7 = Register for Value
      @ r1 = Size of Array
      @ r0 = Address of the 1. Element
      @ r10 = "swapped" register



loop:
     mov r10, #0
     sub r1, #1            @ Decrement Counter for loop



     loop1:

            ldr r5, [r0]
            ldr r7, [r0, #4]


            cmp r5, r7

                  movgt r8, r7
                  movgt r7, r5
                  movgt r5, r8
                  strgt r5, [r0]
                  strgt r7, [r0, #4]
                  movgt r10, #1




            cmp r4, r1   @ compare r4 and r1
            add r4, #1   @ Increment counter for loop1
            blt loop1    @ is r4 < r1 ? yes = go to loop1


     cmp r10, #1
     beq loop

My goal is to sort a sequence of ints or an "array". Given parameters are the address of the first value (r0) and the table size (r1). Load the values from the memory into registers, comparing them, then swap the values in the registers and store them at the right position into the memory.

Before I changed my code I ran the debugger, the "swapping" part in the registers seems to work fine. But im not too sure about the loop-logic I did there. My problem is, when I take a look into the memory, the first value is correctly sorted and then it just stops sorting / ignores the rest.

Now all I get is an endless loop.

I will greatly appreciate any given help.

Also if there is anything I forgot mentioning, just let me know and I will provide it.

Thanks in advance,

Dethe

1
assemblyarm
Since you seem to know how to use the debugger, single step the code and see where it stops instead of continuing or otherwise does something unexpected. PS: your swapping is unnecessarily complicated, no need to swap r5 and r7, just write them out swapped. Also you set r10 to 1 unconditionally which is not what you want probably. – Jester
Yup, looks like I made the swapping redundant and forgot the conditionally changing of r10 to "true". Solved my endless loop problem, but im trying to sort given values = { 9, -8, -7, 6, -5, 4, -3, 2, -1, 0, 127, -128} but when printing the table after sorting im getting crazy values like -6291427 and such. – Dethe
Also you never even change r0 so every iteration will just use the first two elements of the array. That means it sort those two only, then exit either first or second iteration. – Jester
(it's not anymore) – marko

1 Answers

1
votes
@ ---- Added ----
@ bubblesort.s
@
@ pi@RPi3:~ $ as -o bubblesort.o bubblesort.s
@ pi@RPi3:~ $ gcc -o bubblesort bubblesort.o
@ pi@RPi3:~ $ ./bubblesort; echo $?

.data

table:
  .word 9, -8, -7, 6, -5, 4, -3, 2, -1, 0, 127, -128
aft_table:

.balign 4
n:
  .word (aft_table - table) >>2

.text
.global main
main:
     push  {r4-r10, lr}
     ldr   r1, =n
     ldr   r1, [r1]       @ len(table) in r1
@ ---------------

bubblesort:
      @ maybe r0, r1 for table and counter (rest is based on that)
      @ r8 = Buffer for Value
      @ r4 = Counter for loop1
      @ r5 = Register for Value
      @ r7 = Register for Value
      @ r1 = Size of Array
      @ r0 = Address of the 1. Element
      @ r10 = "swapped" register

loop:
     mov r10, #0
     sub r1, #1            @ Decrement Counter for loop

@ ---- Added ----
   ldr   r0, =table
   mov   r4, #1      @ i = 1   i could = 0, if instructions
                     @ cmp r4, r1   @ compare r4 and r1
                     @ add r4, #1   @ Increment counter for loop1
                     @ were reversed
@ ---------------

     loop1:

            ldr r5, [r0]
            ldr r7, [r0, #4]

            cmp r5, r7

                  movgt r8, r7
                  movgt r7, r5
                  movgt r5, r8
                  strgt r5, [r0]
                  strgt r7, [r0, #4]
                  movgt r10, #1

@ ---- Added ----
                  add   r0, #4   @ Index table to next position
@ ---------------

            cmp r4, r1   @ compare r4 and r1
            add r4, #1   @ Increment counter for loop1
            blt loop1    @ is r4 < r1 ? yes = go to loop1

     cmp r10, #1
     beq loop

@ ---- Added ----
exit:
   pop   {r4-r10, lr}
   mov   r0, #0         @ good return code
   bx    lr             @ Exit with gcc linker
@ ---------------

Your code logic is good. I have added several sections to compile and run it, which is marked in your code. Two things to note, mov r4, #1 to start the count, and add r0, #4 to move the table pointer to the next position.

I will also include my debugging scripts that helped with finding errors and help to understand the swap switch (by changing the -128 to 128, less passes through the loops).

@ ---- Added ----
@ bubblesort2.s
@
@ pi@RPi3:~ $ as -o bubblesort2.o bubblesort2.s
@ pi@RPi3:~ $ gcc -o bubblesort2 bubblesort2.o
@ pi@RPi3:~ $ ./bubblesort2; echo $?

.data

table:
  .word 9, -8, -7, 6, -5, 4, -3, 2, -1, 0, 127, 128
aft_table:

.balign 4
n:
  .word (aft_table - table) >>2
@ ---------------

@ ---- Added ----
.balign 4             @ Prt
frmt:                 @ Prt
  .asciz "%d  "       @ Prt

.balign 4
flags:                @ RDmp
  .word 0             @ RDmp
msg:                  @ RDmp
  .asciz "NZCV  2> 6= 8<\n"  @ RDmp
aft_msg:              @ RDmp
                      @ RDmp
l_msg:                @ RDmp
  .word (aft_msg - msg) - 1  @ RDmp
@ ---------------

.text
.global main
.global printf, putchar  @ Prt
main:
     push  {r4-r10, lr}
     ldr   r1, =n
     ldr   r1, [r1]       @ len(table) in r1
     bl    Print          @ Prt
@ ---------------

bubblesort:
      @ maybe r0, r1 for table and counter (rest is based on that)
      @ r8 = Buffer for Value
      @ r4 = Counter for loop1
      @ r5 = Register for Value
      @ r7 = Register for Value
      @ r1 = Size of Array
      @ r0 = Address of the 1. Element
      @ r10 = "swapped" register

loop:
     mov r10, #0
     sub r1, #1            @ Decrement Counter for loop

@ ---- Added ----

   ldr   r0, =table
   mov   r4, #1      @ i = 1   i could = 0, if instructions
                     @ cmp r4, r1   @ compare r4 and r1
                     @ add r4, #1   @ Increment counter for loop1
                     @ were reversed
@ ---------------

     loop1:

            ldr r5, [r0]
            ldr r7, [r0, #4]

            cmp r5, r7

                  movgt r8, r7
                  movgt r7, r5
                  movgt r5, r8
                  strgt r5, [r0]
                  strgt r7, [r0, #4]
                  movgt r10, #1

@ ---- Added ----
                  add   r0, #4   @ Index table to next position
@ ---------------

            cmp r4, r1   @ compare r4 and r1
            add r4, #1   @ Increment counter for loop1
            blt loop1    @ is r4 < r1 ? yes = go to loop1

@ ---- Added ----
     bl    Print         @ Prt
     bl    RDmp          @ RDmp
@ ---------------

     cmp r10, #1
     beq loop

@ ---- Added ----

exit:
   pop   {r4-r10, lr}
   mov   r0, #0         @ good return code
   bx    lr             @ Exit with gcc linker

@ ---------------

@ ---- Added ----

 Print:                  @ Prt, table to stdout
    push  {r0-r10, lr}   @ Prt
    mrs   r10, cpsr      @ Prt
    ldr   r2, =n         @ Prt
    ldr   r2, [r2]       @ Prt
    ldr   r3, =table     @ Prt
 lp:                     @ Prt
    ldr   r0, =frmt      @ Prt
    ldr   r1, [r3], #4   @ Prt
    push  {r0-r3}        @ Prt
    bl    printf         @ Prt
    pop   {r0-r3}        @ Prt
    subs  r2, #1         @ Prt
    bne   lp             @ Prt
    mov   r0, #0xa       @ Prt
    bl    putchar        @ Prt
    msr   cpsr_f, r10    @ Prt
    pop   {r0-r10, lr}   @ Prt
    mov   pc, lr         @ Prt
@ ---------------

@ ---- Added ----
RDmp:                   @ RDmp
   push   {r0-r10, lr}  @ RDmp
   mrs    r10, cpsr     @ RDmp
   push   {r8-r11}      @ RDmp
   push   {r4-r7}       @ RDmp
   push   {r0-r3}       @ RDmp
                        @ RDmp
   ldr    r1, =flags    @ RDmp
   mrs    r0, cpsr      @ RDmp
   str    r0, [r1]      @ RDmp
   b      seq           @ RDmp
                        @ RDmp
p_char:                 @ RDmp
   push   {r0-r4, lr}   @ RDmp
   bl     putchar       @ RDmp
   pop    {r0-r4, lr}   @ RDmp
   mov    pc, lr        @ RDmp
                        @ RDmp
register:               @ RDmp
   mov    r1, #0        @ RDmp
   push   {r0, lr}      @ RDmp
                        @ RDmp
nibble:                 @ RDmp
   mov    r2, r3        @ RDmp
   lsl    r2, r1        @ RDmp
   lsr    r2, #28       @ RDmp
   add    r2, #48       @ RDmp
   cmp    r2, #58       @ RDmp
   addge  r2, #39       @ RDmp
   mov    r0, r2        @ RDmp
   bl     p_char        @ RDmp
   add    r1, #4        @ RDmp
   cmp    r1, #32       @ RDmp
   blt    nibble        @ RDmp
   mov    r0, #32       @ RDmp
   bl     p_char        @ RDmp
   pop    {r0, lr}      @ RDmp
   mov    pc, lr        @ RDmp
                        @ RDmp
manage:                 @ RDmp
   push   {r0, lr}      @ RDmp
   mov    r3, r4        @ RDmp
   bl     register      @ RDmp
   mov    r3, r5        @ RDmp
   bl     register      @ RDmp
   mov    r3, r6        @ RDmp
   bl     register      @ RDmp
   mov    r3, r7        @ RDmp
   bl     register      @ RDmp
   pop    {r0, lr}      @ RDmp
   mov    pc, lr        @ RDmp
                        @ RDmp
seq:                    @ RDmp
   pop    {r4-r7}       @ RDmp
   bl     manage        @ RDmp
   mov    r0, #32       @ RDmp
   bl     p_char        @ RDmp
   pop    {r4-r7}       @ RDmp
   bl     manage        @ RDmp
   mov    r0, #0x0a     @ RDmp
   bl     p_char        @ RDmp
                        @ RDmp
   pop    {r4-r7}       @ RDmp
   bl     manage        @ RDmp
   mov    r0, #32       @ RDmp
   bl     p_char        @ RDmp
   ldr    r3, =flags    @ RDmp
   ldr    r3, [r3]      @ RDmp
   bl     register      @ RDmp
                        @ RDmp
   ldr    r2, = l_msg   @ RDmp
   ldr    r2, [r2]      @ RDmp
   ldr    r1, =msg      @ RDmp
w_msg:                  @ RDmp
   ldr    r0, [r1], #1  @ RDmp
   bl     p_char        @ RDmp
   subs   r2, #1        @ RDmp
   bgt    w_msg         @ RDmp
   msr    cpsr_f, r10   @ RDmp
   pop    {r0-r10, lr}  @ RDmp
   mov    pc, lr        @ RDmp
@ ---------------

The output from ./bubblesort2; echo $?, the lines that start with "@" are my heading comments for the registers below them.

9  -8  -7  6  -5  4  -3  2  -1  0  127  128  
-8  -7  6  -5  4  -3  2  -1  0  9  127  128  
@ (r0)     (r1)     (r2)     (r3)      (r4)     (r5)     (r6)     (r7)
000207f0 0000000b 7ee7077c 00010450  0000000c 0000007f 00010328 00000080 
@ (r8)     (r9)     (r10)    (r11)  (F)(cpsr) (F)   (F val)
00000000 00000000 60000010 00000000  60000010 NZCV  2> 6= 8<
-8  -7  -5  4  -3  2  -1  0  6  9  127  128  
000207ec 0000000a 7ee7077c 00010450  0000000b 00000009 00010328 0000007f 
00000000 00000000 60000010 00000000  60000010 NZCV  2> 6= 8<
-8  -7  -5  -3  2  -1  0  4  6  9  127  128  
000207e8 00000009 7ee7077c 00010450  0000000a 00000006 00010328 00000009 
00000000 00000000 60000010 00000000  60000010 NZCV  2> 6= 8<
-8  -7  -5  -3  -1  0  2  4  6  9  127  128  
000207e4 00000008 7ee7077c 00010450  00000009 00000004 00010328 00000006 
00000000 00000000 60000010 00000000  60000010 NZCV  2> 6= 8<
-8  -7  -5  -3  -1  0  2  4  6  9  127  128  
000207e0 00000007 7ee7077c 00010450  00000008 00000002 00010328 00000004 
00000000 00000000 60000010 00000000  60000010 NZCV  2> 6= 8<
0