G2A Many GEOs
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
Ledger Nano X - The secure hardware wallet
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. OK, I Understand
Top