• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Exercise1_11

Garey Apr 9th, 2020 194 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. // Heapsort
2.
3. // Exported Methods
4.     .global hsort
5.
6. // Code Section
7.
8. hsort:
9.     // R0 = Array location
10.     // R1 = Array length
11.     PUSH    {R2-R12,LR}         // Push registers on to the stack
12.     CMP     R1, #1              // If the array has size 0 or 1, return
13.     BLE     hsort_done
14.     CMP     R1, #2              // If the array has size 2, swap if needed
15.     BLE     hsort_simple
16.     MOV     R11, #1             // R11 = 1 (constant)
17.     MOV     R12, #2             // R12 = 2 (constant)
18.     MOV     R10, #-1            // R10 = -1 (temporarily)
19.     UDIV    R10, R1, R12        // R10 = (len / 2) - 1 (start heapify index)
20.     SUB     R10, R10, #1
21.     SUB     R9, R1, #1          // R9 = len - 1 (start pop index)
22.     MOV     R2, R10             // R2 = Starting heapify index
23. heapify:
24.     // R2 = Index
25.     MOV     R3, R2              // R3 = Index of largest value
26.     MLA     R4, R2, R12, R11    // R4 = Left index (2i+1)
27.     MLA     R5, R2, R12, R12    // R5 = Right index (2i+2)
28.     LDR     R6, [R0, R2, LSL#2] // R6 = Index value (R0 + (R2 * 4))
29.     MOV     R7, R6              // R7 = Current largest value
30. heapify_check_left:
31.     CMP     R4, R9              // Check if left node is in array bounds
32.     BGT     heapify_check_right // If not then check the right node
33.     LDR     R8, [R0, R4, LSL#2] // R8 = Left value (R0 + (R4 * 4)
34.     CMP     R8, R7              // Compare left value to largest value
35.     BLE     heapify_check_right // If left <= largest check right
36.     MOV     R3, R4              // If left > largest, change largest index
37.     MOV     R7, R8              //    and copy the value
38. heapify_check_right:
39.     CMP     R5, R9              // Check if right node is in array bounds
40.     BGT     heapify_swap        // If not then continue
41.     LDR     R8, [R0, R5, LSL#2] // R8 = Right value (R0 + (R5 * 4))
42.     CMP     R8, R7              // Compare right value to largest value
43.     BLE     heapify_swap        // If right <= largest then continue
44.     MOV     R3, R5              // If right > largest, change largest index
45.     MOV     R7, R8              //    and copy the value
46. heapify_swap:
47.     CMP     R2, R3              // Check if largest is the initial value
48.     BEQ     heapify_next        // If so, exit the heapify loop
49.     STR     R7, [R0, R2, LSL#2] // If not, swap largest and initial values
50.     STR     R6, [R0, R3, LSL#2]
51.     MOV     R2, R3              //    and change index to largest index
52.     B       heapify             //    and recurse
53. heapify_next:
54.     CMP     R10, #0             // If last index was 0, heap is finished
55.     BEQ     heapify_pop
56.     SUB     R10, R10, #1        // Else, heapify next index
57.     MOV     R2, R10
58.     B       heapify
59. heapify_pop:
60.     LDR     R3, [R0]            // R3 = Largest value (front of heap)
61.     LDR     R4, [R0, R9, LSL#2] // R4 = Value from end of heap
62.     STR     R3, [R0, R9, LSL#2] // Store largest value at end of heap
63.     STR     R4, [R0]            // Store end value at start of heap
64.     SUB     R9, #1              // Decrement end of heap index
65.     CMP     R9, #1              // If there are only two items left, compare
66.     BEQ     hsort_simple
67.     MOV     R2, #0              // Else, heapify from the start of the heap
68.     B       heapify
69. hsort_simple:
70.     // Sort a list of exactly 2 elements
71.     LDR     R2, [R0]            // First value
72.     LDR     R3, [R0, #4]        // Second value
73.     CMP     R2, R3              // Compare values
74.     STRGT   R3, [R0]            // Swap if out of order
75.     STRGT   R2, [R0, #4]
76. hsort_done:
77.     POP     {R2-R12,PC}         // Return
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top