You are to convert the following C quicksort program to ARM assembler. There are

Question

You are to convert the following C quicksort program to ARM assembler.  There are numerous websites that describe the quicksort algorithm.

Your program must follow these conventions:

A calling function must use a stack to pass arguments to the called function.  When the called function returns, it is the responsibility of the calling function to remove the arguments from the stack.

All registers that a called function will be using to perform calculations must first be pushed onto the stack along with the return address in r14. This is typically the first instruction of the function. When it is time for the function to return, the registers will be restored to their original values.  The return address will be popped into the pc.

You may use any of the 4 stack types.

Make you program scalable so that it is easy to change the array size.

Your quicksort sorts an array of unsigned words (DCD) into ascending order.

Before sorting you will need to copy the array to address 0x40000000.

Here is a C implementation of a quicksort:

void quicksort(unsigned int *arr, int left, int right) {

      int min = (left+right)/2;

      int i = left;

      int j = right;

      int pivot = arr[min];

    while(left<j || i<right)  {

        while(arr[i]<pivot)

            i++;

        while(arr[j]>pivot)

            j--;

        if(i<=j){

           // swap arr[i] with arr[j]

            unsigned int temp = arr[i];

            arr[i] = arr[j];

            arr[j] = temp;

            i++;

            j--;

        } //end if

        else {

            if(left<j)

                quicksort(arr, left, j);

            if(i<right)

                quicksort(arr,i,right);

            return;

        } //end else

    } //end while

}//end quicksort

int main() {

      const int ARRAY_SIZE = 12;

      unsigned int arr[ARRAY_SIZE] = {110, 5, 10, 3 ,22, 100, 1, 23, 6, 12, 654, 1};

      quicksort(arr, 0, ARRAY_SIZE-1);

      return 0;

}

Explanation / Answer

AREA ARMex, CODE, READONLY
; Name this block of code ARMex
ENTRY ; Mark first instruction to execute
start
   LDR   r0, =Array1
   bl qsort
  

qsort:
stmfd sp!, {r4, r6,r1, r2, r3, r5, r7, lr} @ Save r4 and r6 for caller
mov r6, r2 @ r6 <- right
qsort_tailcall_entry:
sub r7, r6, r1 @ If right - left <= 1 (already sorted),
cmp r7, #1
ldmlefd sp!, {r4, r6,r1, r2, r3, r5, r7, pc} @ Return, restoring r4 and r6
ldr r7, [r0, r1, asl #2] @ r7 <- a[left], gets pivot element
add r2, r1, #1 @ l <- left + 1
mov r4, r6 @ r <- right
partition_loop:
ldr r3, [r0, r2, asl #2] @ r3 <- a[l]
cmp r3, r7 @ If a[l] <= pivot_element,
addle r2, r2, #1 @ ... increment l, and
ble partition_test @ ... continue to next iteration.
sub r4, r4, #1 @ Otherwise, decrement r,
ldr r5, [r0, r4, asl #2] @ ... and swap a[l] and a[r].
str r5, [r0, r2, asl #2]
str r3, [r0, r4, asl #2]
partition_test:
cmp r2, r4 @ If l < r,
blt partition_loop @ ... continue iterating.
partition_finish:
sub r2, r2, #1 @ Decrement l
ldr r3, [r0, r2, asl #2] @ Swap a[l] and pivot
str r3, [r0, r1, asl #2]
str r7, [r0, r2, asl #2]
bl qsort @ Call self recursively on left part,
@ with args a (r0), left (r1), r (r2),
@ also preserves r4 and r6
mov r1, r4
b qsort_tailcall_entry @ Tail-call self on right part,
@ with args a (r0), l (r1), right (r6)
END

Thumb_Data           DATA
Array1           DCD       110, 5, 10, 3 ,22, 100, 1, 23, 6, 12, 654, 1

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.