ARM Assembly Merge Sort

@ ANGUEL ESPERANZA


.data
.balign 4
   string1: .asciz "\n l= %d,r=%d"
.balign 4
   string2: .asciz "\n A= %d"
.balign 4
   A:       .skip 512 @128*4
.balign 4
   B:       .skip 512 @128*4
.balign 4
   C:       .skip 512 @128*4
.balign 4
   N:  .word 128

/* CODE SECTION */
.text
.balign 4
.global main
.extern printf
.extern rand


@mergeSort(int arr[], int l, int r)
mergeSort: push {r0,r1,r2,LR}
@    {
     push {r0,r1,r2}
     ldr r0,=string2
     bl printf
     pop {r0,r1,r2}

@    if (l < r)
     cmp r1,r2
     bge mergeSortEnd
@    {
@        // Same as (l+r)/2, but avoids overflow for
@        // large l and h
         push {r1,r2}   @ save L and R
@        int m = l+(r-l)/2;
         sub r2,r2,r1  @ This was a bug (was a 1) int the morning and afternoon versions
         lsr r2,r2,#1
         add r2,r2,r1
         push {r2}  @ save m
@        // Sort first and second halves
@        mergeSort(arr, l, m);   // Remember l is R1, R2 is r=m
         bl mergeSort
         pop {r3}   @ put m into r3
         pop  {r1,r2}  @restored l and r
         push {r1,r2}
         push {r3}
         add  r1,r3,#1
@        mergeSort(arr, m+1, r);
         bl mergeSort
         pop {r3}
         pop  {r1,r2}
@      // Not doing the merge step for now
@      //  merge(arr, l, m, r);








@   >>>>>    Note the formal params are r0=arr,r1=l,r3=m,r2=r <<<<<<<<<<<<<<<<<
@    }
mergeSortEnd: pop {r0,r1,r2,PC}  @ notice put LR into PC to force return
@}







@-------------- MERGE CODE  START ------------------------

@ This line will be copied and paste around the merge function so I do not have to scroll up and down consistantly when writting the code
@r1 -> 'l' | r2 -> 'r' | r3 -> 'm' | r4 -> 'i'; | r5 -> 'j' | r6 -> 'k' | r7 -> 'n1' | r8 -> 'n2' | r9 -> Array B [L] | r10 -> Array C [R] | r11 -> No use| r12 -> No use
@----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
merge:

@    void merge(int arr[], int l, int m, int r)
@{
@    int i, j, k;
    mov r4, #0 @ initilizing 'i'
@    int n1 = m - l + 1;
    mov r7, #0 @ initializing 'r1'
    add r7, r3 @ r3 is 'm'. I added 'm' to n1 first as that way I don't have to push/pop 'm'
    sub r7, r7, r1 @ We are taking l away from m.
    add r7, r7, #1 @ Just adding 1 to the n1
@    int n2 =  r - m;
    mov r8, #0
    add r8, r8, r1 @ Adding r to n2 for the same resason I did m into n1. Doing it this way avoids having to push/pop uncessessarily
    sub r8, r8, r3 @ Just taking m away from r (essentially n2 at this point)
    @^-- Do to the multiple times i've written this code and not knowing where it crashes, i'm going to be making comments periodicaly that will let me know,
    @ the chunk of code up to this point work. This will help when debugging as I know where the last section of working code is.

    @^--- THIS CODE WORKS UP TO THE POINT ABOVE -----^
    @ -----------------------------------------------
@    /* create temp arrays */
@    int L[n1], R[n2];
    @ L[n1] will be array B
    @ R[n2] will be array C
@    /* Copy data to temp arrays L[] and R[] */
@    for (i = 0; i < n1; i++)

@ This line will be copied and paste around the merge function so I do not have to scroll up and down consistantly when writting the code
@r1 -> 'l' | r2 -> 'r' | r3 -> 'm' | r4 -> 'i'; | r5 -> 'j' | r6 -> 'k' | r7 -> 'n1' | r8 -> 'n2' | r9 -> Array B [L] | r10 -> Array C [R] | r11 -> No use| r12 -> No use
@----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

@ This is the for loop that iterates through and does the proper data assignments for L[n1], hence it's name 'forLoopL'
@ For L[n1] I am going to use r4 for indexing and r11 as the index element. I must remember to push/pop after I'm done

    mov r11, #0
    mov r12, #0

    @ I have set those registers outside of the for loop as it will conistently be reset to 0 each time the for loop iteration
@        L[i] = arr[l + i];
@forLoopL is L[i] = arr[l + i]
forLoopL:
    cmp r4, r7 @ checks to see if we have finished out iteration
    bge forLoopLEnd @ Leave the for loop if we are doen iterating
    ldr r9, =B @ Load L[i]
    lsl r11, r4, #2 @ Gets our indexed value offset (i * 4)
    add r11, r9, r11 @ This is the L[i] part of the array. Remember that the array has 128 elements, where each element is 4 bytes long. Thus, we are adding i to our current
                        @ spot in the array.
    str r11, [r11] @ Stores the value of the of our indexed element.
    @^---L[i]

    ldr r0, =A @ Arr load
    lsl r12, r4, #2 @ Gets our index  value offset (i * 4) : I'm doing this again as this element was never added to a register and left untouched.
    add r12, r12, R1 @ We want our value that is at l + i, not just i. Which is why this extra step is done here and not with L[i]
    add r12, r0, r12 @ Getting the memory address in r0 of our desired element
    str r12, [r12] @ Storing the value of our indexed value.

    str r12, [r11] @ Setting L[i] to equal arr[l + i]

    add r4, r4, #1 @ i++

forLoopLEnd:
@^--- THIS CODE WORKS UP TO THE POINT ABOVE ---^
@ -----------------------------------------------


@ This line will be copied and paste around the merge function so I do not have to scroll up and down consistantly when writting the code
@r1 -> 'l' | r2 -> 'r' | r3 -> 'm' | r4 -> 'i'; | r5 -> 'j' | r6 -> 'k' | r7 -> 'n1' | r8 -> 'n2' | r9 -> Array B [L] | r10 -> Array C [R] | r11 -> No use| r12 -> No use
@----------------------------------------------------------------------------------------------------------------------------------------------------------------------------


    mov r11, #0
    mov r12, #0
    @ I'm going to use these for the j for loop. The reason I didn't push them to the stack is because I do not need to save their values. I want to overwrite them.

    @ j was set to 0 earlier in the code.
@    for (j = 0; j < n2; j++)
@        R[j] = arr[m + 1+ j];
forLoopJ:
    cmp r5, r8
    bge forLoopJEnd
    ldr r10, =C
    lsl r11, r5, #2 @ J * 4 indexed element.
    add r11, r10, r11 @ Get the memeory address of our indexed element

    str r11, [r11] @ stores our value into r11
    @ ^-- This is R[j]

    ldr r0, =A
    lsl r12, r8, #2 @ indexed element position in array
    add r12, r12, r3 @ adding m to it
    add r12, r12, #1 @ adding 1 to it
    add r12, r0, r12

    str r12, [r12]

    str r12, [r11]

    add r8, r8, #1

forLoopJEnd:
@^--- THIS CODE WORKS UP TO THE POINT ABOVE ---^
@ ----

@ This line will be copied and paste around the merge function so I do not have to scroll up and down consistantly when writting the code
@r1 -> 'l' | r2 -> 'r' | r3 -> 'm' | r4 -> 'i'; | r5 -> 'j' | r6 -> 'k' | r7 -> 'n1' | r8 -> 'n2' | r9 -> Array B [L] | r10 -> Array C [R] | r11 -> No use| r12 -> No use
@----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

@    /* Merge the temp arrays back into arr[l..r]*/
@    i = 0; // Initial index of first subarray
    mov r4, #0
@    j = 0; // Initial index of second subarray
    mov r5, #0
@    k = l; // Initial index of merged subarray
    mov r6, #0
    add r6, r6, r1 @ After this I am going to pop r1. But before I did, I wanted to make sure I used it for k, which I did.

    mov r11, #0 @ This will be used for L[i]
    mov r12, #0 @ This will be used for R[j]

    push {r1} @ I am going to a register for the while loops. I don't have a spare free one so I chose r1. I need to pop it from the stack after I am done using it though.
                @ r1 -> arr[k]

    @ I didn't push these to the stack before setting them to 0 as I do not need the contents later on.
@    while (i < n1 && j < n2)
whileLoop1:
        cmp r4, r7 @ i < n1
        bge whileLoop1End
        cmp r5, r8 @ j < n2
        bge whileLoop1End
@    {
@
@
@        k++;
@    }

whileLoop1End:

    bl whileLoop2 @ Branch to whileLoop2 and not run the if statements once whileLoop1 is complete

ifStatement:

@ This line will be copied and paste around the merge function so I do not have to scroll up and down consistantly when writting the code
@r1 -> 'l' | r2 -> 'r' | r3 -> 'm' | r4 -> 'i'; | r5 -> 'j' | r6 -> 'k' | r7 -> 'n1' | r8 -> 'n2' | r9 -> Array B [L] | r10 -> Array C [R] | r11 -> No use| r12 -> No use
@----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

@if (L[i] <= R[j])

@       {
@            arr[k] = L[i];
@            i++;
@        }





    @ This code is from an earlier point in the code. There was no point in retyping what I already had so I copied it down.
    ldr r9, =B @ Load L[i]
    lsl r11, r4, #2 @ Gets our indexed value offset (i * 4)
    add r11, r9, r11 @ This is the L[i] part of the array. Remember that the array has 128 elements, where each element is 4 bytes long. Thus, we are adding i to our current
                        @ spot in the array.

    str r11, [r11]
    @^--- L[i]


    ldr r10, =C
    lsl r12, r5, #2 @ J * 4 indexed element.
    add r12, r10, r12 @ Get the memeory address of our indexed element

    str r12, [r12] @ stores our value into r11
    @^--- R[j]

    cmp r11, r12
    bgt elseStatement
    ldr r0, =A
    lsl r1, r6, #2 @ indexed element position in array
    add r1, r0, r1
    str r1, [r1]

    str r11, [r1]

    add r4, r4, #1 @ i++
    add r6, r6, #1 @ k++ | This is done after the forloop has been run. It DOES NOT matter if it was the main for loop, or the else statement. So I am adding it here
                    @ and will add it to the else statement as well.

    bl whileLoop1 @ return back to the while loop




elseStatement:

@ This line will be copied and paste around the merge function so I do not have to scroll up and down consistantly when writting the code
@r1 -> 'l' | r2 -> 'r' | r3 -> 'm' | r4 -> 'i'; | r5 -> 'j' | r6 -> 'k' | r7 -> 'n1' | r8 -> 'n2' | r9 -> Array B [L] | r10 -> Array C [R] | r11 -> No use| r12 -> No use
@----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

@else
@        {
@            arr[k] = R[j];
@            j++;
@        }



    ldr r0, =A
    lsl r1, r6, #2 @ indexed element position in array
    add r1, r0, r1
    str r1, [r1]
    @^--- arr[k]

    str r12, [r1] @ The reason why the array for j is not in else, is because it runs before the else statement has been reached, thus already in memeory.
                    @ remaking it would not make much sense.

    add r5, r5, #1 @ j++
    add r6, r5, #1 @ k++

    bl whileLoop1

@^--- THIS CODE WORKS UP TO THE POINT ABOVE ---^
@ ----


@ This line will be copied and paste around the merge function so I do not have to scroll up and down consistantly when writting the code
@r1 -> 'l' | r2 -> 'r' | r3 -> 'm' | r4 -> 'i'; | r5 -> 'j' | r6 -> 'k' | r7 -> 'n1' | r8 -> 'n2' | r9 -> Array B [L] | r10 -> Array C [R] | r11 -> No use| r12 -> No use
@----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

@ From this point on, most of the code has been copied from earlier spots in this code file.
whileLoop2:

@    /* Copy the remaining elements of L[], if there
@       are any */
@    while (i < n1)
@    {
@        arr[k] = L[i];
@        i++;
@        k++;
@    }

    cmp r4, r7
    bge whileLoop2End

    ldr r9, =B @ Load L[i]
    lsl r11, r4, #2 @ Gets our indexed value offset (i * 4)
    add r11, r9, r11 @ This is the L[i] part of the array. Remember that the array has 128 elements, where each element is 4 bytes long. Thus, we are adding i to our current
                        @ spot in the array.

    str r11, [r11]
    @^---- L[i]

    ldr r0, =A
    lsl r1, r6, #2 @ indexed element position in array
    add r1, r0, r1
    str r1, [r1]
    @^--- arr[k]

    add r4, r4, #1
    add r6, r6, #1

    bl whileLoop2

    str r11, [r1]


whileLoop2End:

whileLoop3:
@    /* Copy the remaining elements of R[], if there
@       are any */
@    while (j < n2)
@    {
@        arr[k] = R[j];
@        j++;
@        k++;
@    }


    ldr r10, =C
    lsl r12, r5, #2 @ J * 4 indexed element.
    add r12, r10, r12 @ Get the memeory address of our indexed element

    str r12, [r12] @ stores our value into r11
    @^--- R[j]

    ldr r0, =A
    lsl r1, r6, #2 @ indexed element position in array
    add r1, r0, r1
    str r1, [r1]
    @^--- arr[k]

    str r12, [r1]

    add r5, r5, #1
    add r6, r6, #1

    bl whileLoop3

@}
whileLoop3End:


    pop {r1} @ at this point, I am done with the merge function and and returning to the mergeSort code

    @bl mergeSort


@-------------- MERGE CODE END --------------------------


@^--- THIS CODE WORKS UP TO THE POINT ABOVE ---^
@ ----


main:
    push    {ip,lr}     @ This is needed to return to the Operating System

    @ldr     r0,=A
    @mov     r1,#0
    @ldr     r2,=N
    @ldr     r2,[r2]

    @bl      mergeSort


    @ This part of the code was copied from OuterLoopWithMerge.s file as it prints out to the screen
    mov r5,#0           @ Print out the array
    ldr r4,=A
printArray:
    ldr r0,=N
    ldr r0,[r0]
    cmp r5, r0
    beq printArrayEnd
    ldr r0,=string2 @ string2 is a data I created to better display the output
    mov r1,r5
    ldr r2,[r4],#4
    bl printf
    add r5, r5, #1

    bl printArray                  /* Go to the beginning of the loop */
printArrayEnd:

    @bl mergeSort


    mov     r0,#0

    pop     {ip, pc}    @ This is the return to the operating system